edited by
477 views
1 votes
1 votes

 L1 = {ambnckd| if(m=n) then (k=l)}

 L2 = {ambnckd| if(n=k) then (k=l)}

which of the above two languages are not cfl ??

how to solve such type of questions?

edited by

1 Answer

2 votes
2 votes

One that can be implemented with PDA (with the help of one stack), will be CFL.

$L_1=\{a^mb^nc^kd^l\, |\, if(m=n)then(k=l)\}$

$L_1$ is CFL , if no of $a's$ = no of $b's$ then we need to ensure no of $c's$ = no of $d's$

Push $a's$ into stack, pop them with $b's$ (as we need to check $m=n$ or not) , now if stack is empty and $c$ is in input, it means $m=n$ holds, now push $c's$ and then pop $c's$ with $d's$ , if stack again goes empty and we have nothing in input it mean $k=l$ (that is what we required) , accepted.

$L_2=\{a^mb^nc^kd^l\, |\, if(n=k)then(k=l)\}$

$L_2$ is not cfl.

Push $a's$ into stack, then Push $b's$ into stack , pop $b's$ with $c's$ (as we need to check $n=k$ or not), suppose $n=k$ holds, means when we get $d$ in input , we have $a's$ on stack. now we have to check $k=l$ , i.e, no of $d's$ = no of $c's$ , it is not possible as we don't have $c's$ now to check it. 

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
3
Çșȇ ʛấẗẻ asked Jul 2, 2023
88 views
0 votes
0 votes
1 answer
4
Srken asked Sep 4, 2022
323 views
How to convert (a+b)* into a minimal Dfa