GATE CS 2011 Q.26 (CS Q.26): Context-Free Grammars, Pushdown Automata and CFLs

Consider the languages $L_1$ , $L_2$ and $L_3$ as given below.

$L_1 = \{0^p 1^q \mid p, q \in \mathbb{N}\}$

$L_2 = \{0^p 1^q \mid p, q \in \mathbb{N} \text{ and } p = q\}$

$L_3 = \{0^p 1^q 0^r \mid p, q, r \in \mathbb{N} \text{ and } p = q = r\}$

Which of the following statements is NOT TRUE?

Push Down Automata (PDA) can be used to recognize $L_1$ and $L_2$

$L_1$ is a regular language

All the three languages are context free

Turing machines can be used to recognize all the languages

Official answer and solution

Solution

Classify languages L1, L2, and L3 within the Chomsky hierarchy.

Language $L_1 = \{0^p 1^q \mid p, q \ge 0\}$ has independent counts $p$ and $q$ , generated by the regular expression $0^* 1^*$ . Therefore, $L_1$ is regular, and any regular language can be recognized by a PDA and a Turing machine.

Language $L_2 = \{0^p 1^p \mid p \ge 0\}$ requires matching a single count between 0s and 1s, which is a deterministic context-free language recognized by a PDA.

Language $L_3 = \{0^p 1^p 0^p \mid p \ge 0\}$ requires simultaneous matching of three counts across separated blocks. By the pumping lemma for context-free languages, $L_3$ is NOT context-free; it is a context-sensitive language recognized by a linear-bounded automaton or Turing machine.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.