Which one of the following languages over Σ={a,b} is NOT context-free?(A) {ww^R | w∈{a,b}*} (B) {wa^

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2019 GATE-CS Theory of Computation paper.

Q: How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2019 question covers Push-Down Automata (PDA) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2019 Theory of Computation question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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} (C) {wa^n w^R b^n | w∈{a,b}*, n≥0} (D) {a^n b^i | i∈{n,3n,5n}, n≥0}

Accepted Answer

Correct Answer: (C) {wa^n w^R b^n | w∈{a,b}*, n≥0} is NOT context-freeConcept: Context-Free Languages and Pumping LemmaOption (A): Even-length palindromes — a classic CFL recognizable by a PDA that pushes the first half and pops against the second half. CFL.Option (B): wa^n b^n w^R — the a^n b^n part can be matched by the PDA stack, and w/w^R matching can be done by reversing w on the stack. CFL.Option (C) — NOT CFL: wa^n w^R b^n requires simultaneously matching w with its reverse (at distance |w| + n) AND matching n a's with n b's. A PDA can use its stack for one matching constraint but not two independent ones simultaneously. A string like (ab)^m a^n (ba)^m b^n requires the PDA to track both m (for w,w^R) and n (for a^n,b^n) independently, which requires two counters — impossible for a single-stack PDA. By the pumping lemma for CFLs (with an appropriately chosen string), this language can be shown to be non-CFL.Option (D): {a^n b^i | i∈{n,3n,5n}} = {a^n b^n} ∪ {a^n b^{3n}} ∪ {a^n b^{5n}}, each of which is a CFL, and the union of finitely many CFLs is CFL.Definition: Context-free languages can be generated by context-free grammars or recognized by pushdown automata (PDA). A PDA has a single stack, so it cannot track two independent counters simultaneously.

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} (C) {wa^n w^R b^n | w∈{a,b}*, n≥0} (D) {a^n b^i | i∈{n,3n,5n}, n≥0}

Master GATE-CS with Our Test Series

More Questions from Push-Down Automata (PDA)

Frequently Asked Questions

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} (C) {wa^n w^R b^n | w∈{a,b}*, n≥0} (D) {a^n b^i | i∈{n,3n,5n}, n≥0}

Master GATE-CS with Our Test Series

More Questions from Push-Down Automata (PDA)

Frequently Asked Questions