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
Link to originalInherently Ambiguous Context-Free Language
A context-free language
is called inherently ambiguous if every context-free grammar that generates is ambiguous.
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
and
Both
and are context-free. However, and this language is not context-free.
One stack is not enough for intersection
Context-free languages can manage one nested dependency well. That is why they are good at patterns such as
. Intersection can force two independent dependencies to hold at the same time. In the standard counterexample, one language requires the
-block and -block to match, while the other requires the -block and -block to match. Their intersection therefore requires all three blocks to match:
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
. This language is context-free. Its complement with respect to
is 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
be a language such that is finite. Then is regular, because every finite language is regular. Regular languages are closed under complement. Hence
is regular. Therefore,
is context-free.