Let \(L=\{0^n1^n|n\ge 0\}\) be a context free language. Which of the following…
2016
Let \(L=\{0^n1^n|n\ge 0\}\) be a context free language. Which of the following is correct?
- A.
\(\overline L\)is context free and\(𝐿^𝑘\)is not context free for any\(𝑘≥1\) - B.
\(\overline L\)is not context free and\(𝐿^𝑘\)is context free for any\(𝑘≥1\) - C.
Both
\(\overline L\)and\(𝐿^𝑘\)for any\(𝑘≥1\)are context free - D.
Both
\(\overline L\)and\(𝐿^𝑘\)for any\(𝑘≥1\)are not context free
Attempted by 38 students.
Show answer & explanation
Correct answer: C
Answer: Both the complement of the language and L^k for any k ≥ 1 are context-free.
Key ideas:
Complement is context-free because the language {0^n1^n | n ≥ 0} is deterministic context-free. A deterministic PDA can push a symbol for each 0 and pop for each 1, accepting exactly the strings with equal numbers of 0s followed by 1s; deterministic context-free languages are closed under complement, so the complement is also context-free.
L^k is context-free because context-free languages are closed under concatenation. For any fixed k ≥ 1, concatenating a context-free language with itself k times yields another context-free language, so L^k is context-free.
Therefore both the complement of L and L^k (for any fixed k ≥ 1) are context-free.
A video solution is available for this question — log in and enroll to watch it.