397 views
2 votes
2 votes
L={xy | x,y€(a+b)* , |x| =|y| , x != y}

How L is cfl? How can I make PDA for this?

2 Answers

Best answer
2 votes
2 votes
First of all lets make a point clear what is x!=y,

if x=y then it could be X^2n or Y^2n and we know we can easily say it’s a Regular beacause we are seeing

pattern of Arthmetic progression (aa,aaaa,aaaaaa,aaaaaaaa) so it will always be CFL beacause every regular is also a CFL.

But they said x!=y, so x^my^n,where m!=n beacause they give that number of x is not equal to number of y

as we know we can draw pda for x^my^n where m=n taking a complement of that will not satisfy

beacause in CFL complement of CFL may or may not be CFL,

So we have to think in other way |X|!=|Y| which means |X|>|Y| or |X|<|Y|

we know union of two CDL is also a CFL,so we can make CFL for |X|>|Y| and |X|<|Y| and union them so we Can say given launguage is CFL.
selected by
0 votes
0 votes
Its definitely CFL but non deterministic CFL. Hence a non-deterministic PD will be made.

Related questions

0 votes
0 votes
0 answers
2
dmacop71 asked Jan 4
100 views
S := 0i := 1L1: if i n goto L2t := i * iS := S + ti := i + 1goto L1L2: return S what is Control FLow Graph for this and GEN KILL for all BB ?
0 votes
0 votes
0 answers
3
0 votes
0 votes
1 answer
4
Ashutosh_98 asked Sep 19, 2021
887 views
If a student prepairing for GATE 2022, then till how many years does he solve the Previous Year Questions?And how many times he have to attempt it ?Please give a strategy...