The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

Best answer

For S1,

c is constant ===> you need to compare w1 with w2 ====> for comparing w1 and w2 you require variable amount of memory ( you can't compare with constant amount of memory ) therefore **it is not RL**

For S2,There is comparission between a and b==>infinite amount of memory required ===> CFL

but now question arises is it DCFL or CFL?

S2 can be re-written as { a^{n} . b^{n} . b^{k} | n ≥ 0, k≥ 1 } U { a^{k}. a^{n} . b^{n} | n ≥ 0, k≥ 3 }

i) { a^{n} . b^{n} . b^{k} | n ≥ 0, k≥ 1 }

x = no.of a's in the string

y = no.of b's in the string

therefore y ≥ x+1 ( note that order of a and b in the strings also important ) ----> DCFL

∴ first push all a's and while getting b, pop a, if b comes on empty stack then String accepted

ii) { a^{k} . a^{n} . b^{n} | n ≥ 0, k≥ 3 }

x = no.of a's in the string

y = no.of b's in the string

therefore x ≥ y+3 ( note that order of a and b in the strings also important ) ----> DCFL

∴ first skip 3 a's and then push all a's and while getting b, pop a, if b's are over then String accepted

**But on UNION of i and ii, it doesn't DCFL** due to

on seeing a you have ambiguity that either push ( for i one ) or skip ( for ii one )

∴ S1 and S2 both are false

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,294 answers

182,250 comments

67,741 users