Context-Free Languages
Short Notes
Context-Free Languages (CFL) are recognized by Pushdown Automata (PDA) and generated by Context-Free Grammars (CFG).
Closure Properties
| Operation | CFL | DCFL |
|---|---|---|
| Union | YES | NO |
| Intersect | NO | NO |
| Complement | NO | YES |
| Reverse | YES | NO |
| Intersect with Regular | YES | YES |
Key Theories & Formulas
1. Ambiguity in Grammar
A CFG is ambiguous if there exists at least one string that has:
- More than one Parse Tree.
- More than one Leftmost Derivation.
- More than one Rightmost Derivation. Note: Checking if a CFG is ambiguous is undecidable.
2. Normal Forms
- Chomsky Normal Form (CNF): \(A \to BC\) or \(A \to a\).
- Greibach Normal Form (GNF): \(A \to a \alpha\).
Example Problems
Problem: Is \(L = \{a^n b^n \mid n \ge 0\}\) a CFL?
- Analysis: Yes. It can be recognized by a PDA that pushes \(a\)s and pops them for \(b\)s.
- Grammar: \(S \to aSb \mid \epsilon\).
Hardest GATE Questions
Topic: Deterministic CFL (DCFL) vs CFL Tricky Question (GATE 2014/2017): Is the language \(L = \{ww^R \mid w \in \{a, b\}^*\}\) a DCFL?
- Analysis: NO. It is a CFL, but not a DCFL. A NPDA is needed to guess where the string \(w\) ends and its reverse \(w^R\) begins.
- The "Trap": \(L = \{wcw^R\}\) is a DCFL because the marker 'c' tells the machine when to start popping.
- Hard Aspect: Intersection logic.
- \(CFL \cap CFL \neq CFL\).
- \(CFL \cap Regular = CFL\).
- Complexity: Proving a language is not CFL using the Pumping Lemma for CFLs (\(uvwxy\) split).
- \(L = \{a^n b^n c^n\}\) is the classic example of a Non-CFL (CSL)