Gate2019 cs Q41
0. Which one of the following languages over Σ = {a, b}is NOT context-free?
- Option : C
- Explanation : (a) {wwR |w ∈ {a, b}* } is a CFL (b) {wan bn wR |w ∈ {a, b}*, n ≥ 0} is a CFL, since we can first push w, then a’s, b’s pop with a’s and wR pops with the w. So PDA can accept the language. (c) {wanwR bn|w ∈ {a, b}*, n ≥ 0} is a not CFL because after pushing w, we need to push a’s into stack which will stop the w from being matched with wR. If we don’t push a’s after w, than later we cannot match with bn. So this language is not acceptable by a PDA and hence not a CFL. (d) {anbi |i ∈ {n, 3n, 5n}, n ≥ 0} = anbn∪ anb3n∪ anb5n is CFL since each of the three parts is a CFL and closure under union guarantees that result also is a CFL.
