in Theory of Computation
614 views
2 votes
2 votes

Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct?

  1. $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$
  2. $\overline L$ is not context free and $L^k$ is context free for any $k\ge1$
  3. Both $\overline L$ and $L^k$ for any $k\ge1$ are context free
  4. Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free
in Theory of Computation
614 views

3 Answers

1 vote
1 vote
L is DCFL.

DCFLs are closed under complement. so L^(complement of L) is DCFL => L^ is context free.

L^k is concatenation of CFLs. CFLs are closed under this property, so L^k is context free.
0 votes
0 votes

Complement of CDL is not CFL. Also L^k becomes (0^n 1^n)^k will be both regular and context free. Hence option B is correct

0 votes
0 votes
Ans is C.

The given Language  L=$ {0^n^1n|nā‰„0} $ is DCFL. and

DCFL is Closed under Complementation, Kleen Closure, Union and Concatenation.

so the correct ans is C.
Answer:

Related questions