2 votes 2 votes Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct? $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$ $\overline L$ is not context free and $L^k$ is context free for any $k\ge1$ Both $\overline L$ and $L^k$ for any $k\ge1$ are context free Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free Theory of Computation ugcnetcse-june2016-paper3 context-free-language + – soujanyareddy13 asked May 10, 2021 soujanyareddy13 639 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. Amartyap answered May 11, 2021 Amartyap comment Share Follow See all 0 reply Please log in or register to add a comment.
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 rish1602 answered Jul 12, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.
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. TheShivam answered Aug 22, 2021 TheShivam comment Share Follow See all 0 reply Please log in or register to add a comment.