Which one of the following languages over Σ={a,b} is NOT context-free?
- A{ww^R | w∈{a,b}*}
- B{wa^n b^n w^R | w∈{a,b}*, n≥0}
- {wa^n w^R b^n | w∈{a,b}*, n≥0}
- D{a^n b^i | i∈{n,3n,5n}, n≥0}
Explanation
A is the classic even-length-palindrome CFL. B is context-free: a single stack can push w then a^n (in that order), pop n a's while matching n b's, then continue popping the remaining w to match w^R — a properly NESTED dependency structure. D is a union of 3 simple counting CFLs, and CFLs are closed under union. But C requires matching w against w^R (centered around the middle) AND SEPARATELY matching a^n against b^n, where the a^n block sits BETWEEN w and w^R while b^n comes AFTER w^R — this creates a CROSSING dependency that a single stack cannot handle (by the time b^n is read, the stack has already been consumed matching w against w^R, with nothing left to compare against the a^n count). This is the standard non-context-free construction.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.