Context-Free Language

A context-free language is a language that can be generated by a context-free grammar (CFG).

Definition §

Context-free Language

Let $L$ be a language. Then:

$$\text{L is context-free}⟺\exists \text{ CFG }G\text{ s.t. }L(G)=L$$

Inherently Ambiguous Language

A context-free language $L$ is inherently ambiguous if every CFG that generates it is ambiguous.

Theorems §

T1: Every regular language is context-free

Let $L$ be a language.

$$\text{L is regular}⟹\text{L is context-free}$$

Example

Note

#todo https://williamumboh.com/comp30026-2025/cfg/#regular-languages-are-context-free

In fact, we can restrict CF languages’ production rules to ensure they have no recursion to get them to degenerate to regular languages.

T:3 Every CF language can be recognised by a PDA

Let $L$ be a context-free language. Then there exists a pushdown automata that can accept all the words in the language:

$$\exists \text{PDA},P\text{ s.t. }L(P)=L$$

T2: Context-free Languages are closed under union ^t2

Let $A,B$ be two context-free languages. Then, the union (with respect to languages), is also context-free:

$$\text{A,B are CF}⟹A\cup B\text{ is CF}$$

Proof

Let $A$ and $B$ be two context-free languages (over the same alphabet $\Sigma$) generated by $G_A$ and $G_B$.

Then $G_A=(\Sigma ,V_A,R_A,S_A)$ and $G_B=(\Sigma ,V_B,R_B,S_B)$. If we manage to construct a grammar that generates $A\cup B$, then that is good enough to show that the language is context-free.

Let $H$ be this new grammar. It would need to have variables and production rules from both languages plus some additional stuff, and this would be very similar to proving the union of regular languages are regular.

Then:

• $V_H=V_A\cup V_B\cup \{S_H\}$
• $R_H=R_A\cup R_B$ and also the new production rules $S_H\to S_A$ and $S_H\to S_B$.
• Again, this is similar to using epsilon transitions when proving regularity of a union of languages.
• $S_H$ is the starting variable for $H$

This grammar $H$ then generates word from both $A$ and $B$ and hence proves $A\cup B$ is context-free.

T4: Context-free languages are closed under concatenation ^t4

Let $A,B$ be two regular languages. Then, the operation of concatenation preserves regularity:

$$\text{A,B are regular}⟹A\circ B\text{ is regular}$$

T5: Context-free languages are closed under Kleene star ^t5

Let $L$ be a regular language. Then, the Kleene star operation preserves regularity:

$$\text{L is regular}⟹\text{L∗ is regular}$$

#todo https://williamumboh.com/comp30026-2025/cfg/#closure-properties

make proofs

T6: More context-free-preserving operations #TODO ^t6

The following operations all preserve regularity:

• Reversal