The Gateway to Computer Science Excellence

+5 votes

Best answer

This language can be decomposed into 3 parts :

Let the first part be : a)* La = { a^{n} b^{m }| m < n } * which we know is decidable

b)* Lb = { a^{n} b^{m} | n < m < 2n } *..Now this can be further decomposed as : { a

Now each of the components mentioned above are DCFLs..However if we take union , we can clearly see non determinism as soon as 'a' is finished scanning and 'b' comes in the input..Hence this part is not DCFL but yes it is NDCFL as only one of the above needs to be followed at a time..

c)* Lc = { a^{n} b^{m} | m > 2n } *which is again a DCFL..

So the given language L1 in the question is nothing but the union of the above 3 cases as the both the language conditions given in the question m != n and m != 2n are met by the above explained 3 cases and also all strings will be covered..

Hence for deciding language class , we do nothing but union of a) , b) and c) cases which are DCFL , NDCFL and DCFL respectively..

**Hence the union is going to be a NDCFL language..**

**Hence L1 is NDCFL**

- 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,356 answers

198,482 comments

105,254 users