2,253 views
2 votes
2 votes

Following is the PDA that accept equal number of a and b.

How can this be converted to DPDA? When stack top is Z,that it can read epsillon or a or b,which can create choice.So how can i remove choice in this and make it deterministic?

2 Answers

1 votes
1 votes

As I know machine will confuse only when there is single input and more than one output state. As you have written the inputs are a,$\epsilon$ which are different there is no confusion for machine. Take example of even length palindrome string, here your pda can't decide whether to go to $q_{0} or q_{1}$ on input a. Hence it is NPDA.

0 votes
0 votes
In above case only one choice is selected at a time which does not confuse the machine hence it is DPDA only. The grammar for which it is constructed is (a+b)* thus even $\epsilon$ is acceptd which is true in given PDA. It is called NPDA only when situation is for same input, you have push option and pop option like (a,a/aa) and (a,a/$\epsilon$) at one state only which is not a case here. So given question is already in DPDA.

Related questions

0 votes
0 votes
1 answer
2
Rahul Jain25 asked Feb 9, 2017
850 views
A DPDA can have dead configurations?? True/False.I think answer should be true bcoz DPDA requires that for a combination of top symbol and input at each state there is un...
0 votes
0 votes
1 answer
3