find which of the following CFL which are not, plz discuss one by one..

Question

1. L={ai bj ck | k=max{i,j}} 2. L={0n 1m | m≤n2} 3. L={0n 1m | m≠n2} 4. {0n 1m |m≠n, m≠2n, m≠3n} 5. {ai bj ck| i≠j or j≠k or i≠k} 6. {0,1}*-{(0n 1)n | n≥1} 7. {ai bj | 2i=3j} 8. if L is regular then Lc={xz | (∃y)[|x|=|y|=|z|, xyz∈L]} is?? 9. L={0,1}*-{(0m 1m)n | m,n≥1}

Answer 1

1) L={aⁱbj ck | k=max{i,j}} is not CFL. As it not satisfying prefix property

2) Not CFL.

L={0n 1m | m≤n2}

Cannot draw PDA for it

3)Not CFL.

L={0n 1m | m≠n2}

Same as previous

4)Yes CFL.

{0n 1m |m≠n, m≠2n, m≠3n}  

Here 3 condition satisfying in a CFL

5)Yes it is NCFL

{ai bj ck| i≠j or j≠k or i≠k} union of CFL are NCFL

6) Not CFL

L={0,1}*-{(0n 1)n | n≥1}

(0n 1)ⁿ cannot be done in one stack

7)Yes it is CFL.

L={ai bj | 2i=3j}

S->aaSbbb/aabbb

8)Yes CFL.

 Lc={xz | (∃y)[|x|=|y|=|z|, xyz∈L]} ,

Here L=xⁿyⁿzⁿ  i.e. CSL.

Now L^c=(x+y+z)^* - xⁿzⁿ = {xⁱy^jz^k | i!=k}

9) Not CFL. L={0,1}*-{(0m 1m)n | m,n≥1} =regular - CFL

                                                                    =regular ⋂ (CFL)'

                                                                   = regular ⋂ recursive = recursive