Consider the following statements with respect to the language \(L = \{ a^n…
2019
Consider the following statements with respect to the language \(L = \{ a^n b^n \mid n \geq 0 \}\)
\(𝑆_1\): \(𝐿^2\) is a context free language
\(𝑆_2\):\(𝐿^𝑘\) is context free language for any given \(𝑘≥1\).
\(𝑆_3\): \( \overline{L}\) and \(𝐿^∗\) are context free languages
Which one of the following is correct?
- A.
only
\(𝑆_1\)and\(𝑆_2\) - B.
only 𝑆1 and
\(𝑆_3\) - C.
only
\(𝑆_2\)and\(𝑆_3\) - D.
\(𝑆_1\),\(𝑆_2\)and\(𝑆_3\)
Attempted by 28 students.
Show answer & explanation
Correct answer: D
Answer: All three statements are true.
Key points and brief justifications:
S1: L^2 = { a^n b^n a^m b^m | n,m ≥ 0 } is context-free because context-free languages are closed under concatenation. You can build a grammar or combine two PDAs to generate or recognize two copies in sequence.
S2: For any finite k ≥ 1, L^k is a finite concatenation of L with itself. Since CFLs are closed under finite concatenation, L^k is context-free.
S3: L* is context-free because CFLs are closed under Kleene star (one can construct a grammar for the star from a grammar for L). The complement of L is context-free because L = { a^n b^n } is a deterministic context-free language (a DPDA can push for each a and then pop for each b, switching at the first b); deterministic context-free languages are closed under complement. Note that general CFLs need not be closed under complement, but this language is an exception due to determinism.
A video solution is available for this question — log in and enroll to watch it.