L1 and L2 ?

But still I have a doubt about third one.

The Gateway to Computer Science Excellence

+2 votes

+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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,445 users