124 views

edited | 124 views
+1
2 CFL

L1 and L2 ?

But still I have a doubt about third one.
0
3..?
+1
2

L3 not CFL because we have to compare i!=j and 1st a= 2nd a......two comparison so     non-CFL
0
@hacker16 no bro the correct answer is 2 L1 and L2 are context free
+1
@Draj95 thanks bro i was confused with 3rd option because i was thinking we can ignore middle j numbers of elements but didn't get second condition so i was thinking that it is context free

Ans should be 2

L1 : CFL

Reason: Context free grammar for this language

S--> 0S1 / 1S0 / 0S0 / 1S1 / 0

(ODD) 0 (ODD) = ODD length strings

(Even) 0 (Even) = ODD length strings

L2: CFL ( easily you can visualise )

L3: CSL ( because here Total comparison >= 2 for same symbol. 1comparison:  first time number 'a' should be equal to last time number of 'a'. 2 comparison: 'b' in middle should not equal to the number of 'a'.)

Please let know if I am wrong.

by Active (2k points)
selected
0
i get u bro but i have a stupid doubt which is for L2 because i!=j or j!=k because this is or so there is also two comparisons so how it is context free @thepeeyoosh
+2

okk, Let's take some assumption to understand this language.

i!=j (assume A)  "OR"   j!=k ( assume B

we know that A OR B must be true if at least one is true either( A or B or BOTH). Here PDA is possible but DPDA is not. For making both simultaneously true in the PDA, you have the choice to accept the string either A side or B side in PDA.

0
Yes u r right thanks for clearing doubt
+1 vote
Language L1 and L2 (Or is given ) are CFL in L3 we have to check First that number of "A" should not be equal to number of "B" from both side. Hence only two language are CFL please correct me if I am wrong
by Active (4.2k points)