Consider the following languages. \(L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0…
2013
Consider the following languages.
\(L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0 \right \}\)
\(L_2 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0, p\neq r \right \}\)
Which one of the following statements is FALSE?
- A.
\(L_2\)is context-free. - B.
\(L_1∩ L_2\)is context-free. - C.
Complement of
\(L_2\)is recursive. - D.
Complement of
\(L_1\)is context-free but not regular.
Attempted by 87 students.
Show answer & explanation
Correct answer: D
Correct statement that is FALSE: Complement of L1 is context-free but not regular.
Key fact: L1 = 0*1*0* is regular (it is described by the regular expression 0*1*0*).
Consequence: the complement of a regular language is regular (and therefore also context-free).
Therefore the statement that the complement of L1 is "context-free but not regular" is false, because the complement is regular.
Additional notes: L2 is context-free because it can be written as the union of two context-free languages (strings with p>r and strings with p<r), and complement(L2) is recursive because L2 is decidable.
A video solution is available for this question — log in and enroll to watch it.