AEiE0802 Context free language¶
CFG and CFL fundamentals¶
- A context-free grammar (CFG) generates strings by replacing one nonterminal at a time.
- A context-free language (CFL) is any language generated by some CFG.
- A parse tree shows the hierarchical derivation of a string.
- A pushdown automaton (PDA) is a finite automaton equipped with a stack.
- CFL and PDA are equivalent in expressive power.
Formal grammar form:
\[
G=(V, \Sigma, P, S)
\]
- \(V\): variables or nonterminals.
- \(\Sigma\): terminal alphabet.
- \(P\): production rules.
- \(S\): start symbol.
Typical context-free rule form:
\[
A \to \alpha
\]
where \(A\) is one nonterminal and \(\alpha\) is any string of terminals and nonterminals.
Derivation and parse-tree cues¶
| Term | Meaning | Recognition cue |
|---|---|---|
| Leftmost derivation | Expand leftmost nonterminal first | Top-down parsing view |
| Rightmost derivation | Expand rightmost nonterminal first | Bottom-up relation |
| Parse tree | Tree of one complete derivation | Same tree may permit different derivation orders |
| Language of grammar | All terminal strings derivable from \(S\) | Ignore partial sentential forms |
- Top-down parsing builds from the start symbol to the string.
- Bottom-up parsing reduces the string back to the start symbol.
- Leaves of a parse tree are terminals or epsilon; internal nodes are nonterminals.
Ambiguity and CNF¶
- A grammar is ambiguous if some string has more than one distinct parse tree.
- Equivalent warning sign: one string has more than one leftmost derivation.
- Classic example: \(E \to E+E \mid E*E \mid id\).
In CNF, productions are mainly restricted to:
\[
A \to BC \qquad \text{or} \qquad A \to a
\]
plus optionally \(S \to \varepsilon\) when the language contains the empty string.
- CNF conversion usually removes epsilon-productions, unit productions, and useless symbols.
- CNF changes the grammar form, not the generated CFL.
PDA equivalence and CFL properties¶
| Feature | Finite automaton | PDA |
|---|---|---|
| Memory | Finite control only | Finite control plus unbounded stack |
| Typical strength | Regular languages | Context-free languages |
| Recognition cue | No nesting count | Can match nested structure |
- The stack is why a PDA can recognize balanced parentheses.
- A single stack is enough for CFLs.
- Two unrestricted stacks make the model Turing-equivalent in power.
CFL closure facts:
- Closed under union, concatenation, Kleene star, reversal, homomorphism, and inverse homomorphism.
- Not closed under intersection or complement in general.
- Closed under intersection with a regular language.
Under the standard exam convention, the language hierarchy is
\[
ext{regular}\subsetneq\text{context-free}\subsetneq\text{context-sensitive}
\subsetneq\text{recursive}\subsetneq\text{recursively enumerable}.
\]
Thus every context-free language is context-sensitive, but not every context-sensitive language is context-free.
Standard examples for context-free language¶
| Language | Type | Why |
|---|---|---|
| \(\{a^n b^n \mid n \ge 0\}\) | CFL, not regular | Needs one stack count |
| Balanced parentheses | CFL | Natural PDA stack language |
| \(\{ww \mid w \in \{0,1\}^*\}\) | Not CFL | Exact duplication is too strong for one stack |
Common traps in context-free language¶
- CFG and CFL are not the same object: grammar versus language.
- Not every PDA is deterministic.
- CNF is a restricted equivalent grammar form, not a smaller language.
- Bottom-up and top-down are parsing strategies, not different language classes.
- A grammar can be unambiguous and still not be in CNF.
One-step examples for context-free language¶
- Grammar \(S \to aSb \mid \varepsilon\) generates \(\{a^n b^n\}\).
- For string aabb, one leftmost derivation is \(S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb\).
- A PDA recognizes balanced parentheses by pushing for each left parenthesis and popping for each right parenthesis.
Context-free-language revision box¶
CFG generates a CFL. PDA recognizes exactly the CFLs. Parse trees capture structure. Ambiguity means more than one parse tree for the same string. CNF keeps the language but restricts rule shapes.