GATE CS 2021 (Afternoon) — Question 51

Theory of Computation (TOC)Regular and Context-Free Languages & Pumping LemmaMSQ2 marksMedium

For a string \(w\), we define \(w^R\) to be the reverse of \(w\). For example, if \(w = 01101\) then \(w^R = 10110\). Which of the following languages is/are context-free?
  1. A
    \(\{wxw^R x^R \mid w, x \in \{0, 1\}^*\}\)
  2. B
    \(\{ww^R xx^R \mid w, x \in \{0, 1\}^*\}\)
  3. C
    \(\{wxw^R \mid w, x \in \{0, 1\}^*\}\)
  4. D
    \(\{wxxw^R w^R \mid w, x \in \{0, 1\}^*\}\)
Practise the full 2021-AN 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