34 views

edited | 34 views

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 { an . bn . bk | n ≥ 0, k≥ 1 } U { ak. an . bn | n ≥ 0, k≥ 3 }

i)   { an . bn . bk | 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)   { ak  . an . bn | 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