Consider the languages \(L1, \:L2 \) and \( L3\) as given below. \(L1=\{a^p…
2011
Consider the languages \(L1, \:L2 \) and \( L3\) as given below.
\(L1=\{a^p b^q \mid p, q \in N\},\\ L2 = \{a^p b^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{a^p b^q c^r \mid p, q, r \in N\: and \: p=q=r\}.\)
Which of the following statements is NOT TRUE?
- A.
Push Down Automata (PDA) can be used to recognize
\(L_1\)and\(L_2\) - B.
\(L_1\)is a regular language - C.
All the three languages are context free
- D.
Turing machines can be used to recognize all the languages
Attempted by 99 students.
Show answer & explanation
Correct answer: C
Correct answer: The statement "All the three languages are context free" is not true.
L1: L1 = a* b* is regular (for example, described by the regular expression a*b*), so it is context-free and recognizable by a PDA (and by a finite automaton).
L2: L2 = {a^n b^n} is a standard context-free language (for example generated by the grammar S → a S b | ε) and is recognized by a PDA that pushes each a and pops for each b.
L3: L3 = {a^n b^n c^n} is not context-free. Sketch of a proof using the pumping lemma for context-free languages: take a string s = a^p b^p c^p where p is the pumping length. Any valid decomposition required by the lemma places the pumped pieces within at most two of the three blocks; pumping changes the counts in those blocks but not the third block, so after pumping the three counts cannot all remain equal. This contradiction shows L3 is not context-free.
Therefore the statement that all three languages are context-free is false because L3 is not context-free; the other statements about PDA recognition, L1 being regular, and Turing machines recognizing all languages are true.
A video solution is available for this question — log in and enroll to watch it.