GATE CS 2019 (Forenoon) — Question 41

Theory of Computation (TOC)Regular and Context-Free Languages & Pumping LemmaMCQ2 marks · −2/3 if wrongMedium

Which one of the following languages over \( \Sigma = \{a, b\} \) is NOT context-free?
  1. A
    \( \{ww^R \mid w \in \{a, b\}^*\} \)
  2. B
    \( \{wa^nb^nw^R \mid w \in \{a, b\}^*, n \ge 0\} \)
  3. C
    \( \{wa^nw^Rb^n \mid w \in \{a, b\}^*, n \ge 0\} \)
  4. D
    \( \{a^nb^i \mid i \in \{n, 3n, 5n\}, n \ge 0\} \)
Practise the full 2019-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Regular and Context-Free Languages & Pumping LemmaTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group