in Theory of Computation
1,314 views
4 votes
4 votes

L={anbpcan   ∣p,n>0}∪{anbpdbp   ∣p,n>0}

in Theory of Computation
1.3k views

1 comment

yes it is DCFL.
2
2

1 Answer

0 votes
0 votes
Best answer

Yes it's DCFL.

1. Push all a's and b's
2. if c comes, then ignore this c and pop all the b's
3. when a's come again, pop one 'a' from stack for every input 'a'
4. input is completed and stack contains stack contains stack symbol on TOS, accept the language.

1. Push all a's and b's
2. if d comes, then ignore this d
3. when b's come again, pop one 'b'  from stack for every input 'b'
4. input is completed and stack contains 'a' on the top of the stack, then accept the language

selected

4 Comments

Can any one explain how do we pop b’s when c comes as there is only one c ?
0
0
It's not Dpda...pop for all 'b' we need epsilon transition which make Npda..
0
0
Everyone make one mistake violating of definition of Dpda like if (q, epsilon,x) != Phi then (q,a,x)=phi…

If maintain this rule then your machine will deternistic otherwise it is nondeterministic…

Your mistake is when popping 'b' your transition should be (q2,epsilon,b)=(q2, epsilon) which makes Npda.... otherwise how you popping 'b' means in which symbol against you needed for popping 'b' only possible with epsilon...

Your machine is Dpda with epsilon transition... implies Npda..

https://cstheory.stackexchange.com/questions/32271/are-dpdas-without-a-epsilon-moves-as-powerful-as-dpdas-with-them
0
0

Related questions