The Gateway to Computer Science Excellence
+2 votes
125 views

in Theory of Computation by Boss (11.7k points)
edited by | 125 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

2 Answers

+4 votes
Best answer

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 by
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)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
198,594 comments
105,445 users