The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
31 views

Please help me to find which are true?

asked in Theory of Computation by (357 points)
edited by | 31 views

1 Answer

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

answered by Boss (41.5k points)
selected by
0
both s1 and s2 are false.nice explanation

No related questions found



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,072 questions
49,594 answers
162,956 comments
65,787 users