Question

Note: Please show/explain all cases clearly for the pumping lemma and describe how your Turing machine works for each state transition. Problem 1: Non-context-free languages and Tining Machine Models B5] context-free: 쉑: Use the pumping lemma for context-free languages to show that the following language A is not a. Use the pumping lemma for context-free languages to show that the following language A = {oilok l o l

SUBJECT:THEORY OF COMPUTATION

CAN SOMEONE PLEASE HELP ME I HAVE POSTED IT REPEATEDLY AND I KEEP GEETING INCOMPLETE / INCORRECT ANSWER . I WILL GIVE YOU A HIGH REVIEW IF YOU HELP ME AND IT IS DONE PROPERLY !

Answer 1

1. Use puming lemma for CFL to prove A is not Context Free:

Pumping Lemma for context free language states that If L is a Context free language, then for all s $\in$ L such that |s|>= n, for some integer n, we can v,w,x,y,z such that s = vwxyz and

1. |wxy| <= n
2. |wy| >=1
3. for all i>= 0, vwⁱxyⁱz  $\in$ L

Proof: Let s = 001110000 $\in$ A and n=9

Let v= 0, w=0, x=1, y=1 z =10000

so, s = vwxyz

Now, lets check the conditions:

1. |wxy|<=n   
2. |wy| >=1
3. for all i=2
   vwⁱxyⁱz = 00011110000 $\notin$ A .

Hence, A is not a context free language.

2. Let L1 = aⁱb^jc^k | i<j ,i,j,k>=0 and L1 is a context free language and

L2 = aⁱb^jc^k | j<k ,i,j,k>=0 and L2 is also a context free language and

L1 $\cap$ L2 = A and A is not a context free language which is an intersection of two context free languages(L1 and L2) . Hence, Context free languages are not closed under intersection.

3.Using the above result , Intersection of L1 and L2 can be written as

$\overline{}$
L1U L2
= $L1 \cap L2$ ......................equation(1)

We will prove it by contradiction. CFLs are closed under union and lets assume CFLs are closed under complement. If CFLs are closed under complement then CFLs are closed under intersection also (by equation 1) which is false.

Hence, CFLs are not closed under complementation.

4.
Page, niHal Stata nl Sate' Sae Tranritions メ,R 2 L. Sdanned with sca re

Go,2) cs canned with CamScanner

에 지 R) ㄟㄅㄧㄅ U,LR. Scahneb with Scanrer :)-レーレ 1 5