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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,927 questions

47,580 answers

146,436 comments

62,311 users