#ugc-2016 #question 56

Question

Let L = {0ⁿ1ⁿ | n≥0} be a context free language.

Which of the following is correct?

(A) L’ is context free and L^k is not context free for any k≥1

(B) L’ is not context free and L^k is context free for any k≥1

(C) Both L’ and L^k is for any k≥1 are context free.

(D) Both L’ and L^k is for any k≥1 are not context free.

Official answer given by UGC is C . according to me answer is B 

Comments

please check this link

https://www.cs.wcupa.edu/rkline/fcs/cfl-pump.html

cfl is not closed under complement

---

yes..sorry,CFL are nto closed..

---

CFL not closed under compliment doesnot mean no CFL whose complement is CFL.

Answer 1

option 3 is correct complement of L1  will also have strings like  L = 1ⁿ0ⁿ                                          in general we can make a CFG of complement of  L = {0ⁿ1ⁿ | n≥0} as below

S → T | aU | V b

T → aT | T a | bT | T b | ba

U → aU | W

V → V b | W

W → aW b | λ

and  L = {0ⁿ1ⁿ | n≥0} is also context free (push 0 and pop 1 into stackand at last we have empty string)

so both L1 and L2  are context free

Comments

Sir how to solve these problems like

Given L is regular , L' is regular or not

Given L is CFL , L' is CFL or not

Can you please say

---

According to closure properties chart DCFL are closed under the complimentations but CFL's are not.

L= 0ⁿ1ⁿ | n≥0 is DCFL so L' will also be DCFL.  Again L^k is for any k≥1 means L to power any k≥1 should not be DCFL because DCFL's are not closed under union. where I am wrong Sir? 

 

Answer 2

given L={0^n 1^n | n≥0}
complement of L = L1 U L2
where L1={not of form 0^i 1^j } and L2={0^i 1^j , i≠j } for i>0,j>0.

now complement of L1 = {of the form 0^i 1^j  } so it will be regular as automata can read all 0's and then all 1's in next state. L1 will also be regular as L1' is regular(regular lang closed under complement).so if L1 is regular it is also CFL.

L2 = L3 U L4
where L3 = {0^i 1^j , i>j } and L4= {0^i 1^j , i<j }

grammar for L3(more 0's then 1's) will be S → AS1 , A → aA|a , S1→ aS1b|λ
similarly can be done for L4

so L3,L4 are CFL then under union L2 will also be CFL.

so L' = L1 U L2 will be CFL

https://www.youtube.com/watch?v=9pDdSxxJJ-k&list=PLbMVogVj5nJSd25WnSU144ZyGmsqjuKr3&index=28
watch from 28 : 00