Context-Free Language

languages

Definition

Context-Free Language

A formal language is called context-free if it can be generated by a context-free grammar.

Equivalently, it is a language accepted by a pushdown automaton.

Inherent Ambiguity

Definition

Inherently Ambiguous Context-Free Language

A context-free language $L$ is called inherently ambiguous if every context-free grammar that generates $L$ is ambiguous.

Link to original

Closure

Context-free languages are closed under:

• union, concatenation, and star,
• homomorphism
• intersection with regular languages.

They are not closed under:

• intersection in general,
• complement.

Counterexample for intersection

Let

$$L_1=\{a^m{b}^m{c}^n\mid m,n\ge 0\}$$

and

$$L_2=\{a^m{b}^n{c}^n\mid m,n\ge 0\}.$$

Both $L_1$ and $L_2$ are context-free. However,

$$L_1\cap L_2=\{a^n{b}^n{c}^n\mid n\ge 0\}$$

and this language is not context-free.

One stack is not enough for intersection $a^n{b}^n$.

Intersection can force two independent dependencies to hold at the same time. In the standard counterexample, one language requires the $a$-block and $b$-block to match, while the other requires the $b$-block and $c$-block to match.

Their intersection therefore requires all three blocks to match:

$$a^n{b}^n{c}^n$$

This is beyond what one pushdown automaton can handle. A useful memory aid is: intersection would force two stacks, and CFLs only have one.

Examples

Complement need not be infinite

The statement that the complement of every context-free language is always infinite is false.

Let $L={\Sigma }^{\ast }$. This language is context-free.

Its complement with respect to ${\Sigma }^{\ast }$ is

$$\overline{L}=\varnothing$$

which is finite.

Therefore, the complement of a context-free language is not necessarily infinite.

Finite complement

Every language with finite complement is context-free.

Let $L$ be a language such that $\overline{L}$ is finite. Then $\overline{L}$ is regular, because every finite language is regular.

Regular languages are closed under complement. Hence $L$ is regular.

Therefore, $L$ is context-free.