World's most popular travel blog for travel bloggers.

[Solved]: Why is this NPDA?

, , No Comments
Problem Detail: 

enter image description here

I am studying PDA at the moment, and I came up with this question.

The figure above tells me that although both PDA accept the same language, one is non-deterministic and the other is deterministic. I don't understand the reason why the first one in non-deterministic. As far as I know, the conditions for DPDA is that

1) every transition should have at most one move

2) if $\delta$(q,a,X) is not empty, then $\delta$(q,$\epsilon$,X) should be empty.

However, since the first PDA does satisfy the above conditions therefore I thought it is DPDA.

What am I missing?

Thanks in advance.

Asked By : Mansumen

Answered By : Renato Sanhueza

The first PDA doesn't comply the second condition because $|\delta (q0,a,\epsilon)| = |\delta (q0,\epsilon,\epsilon)| = 1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51477

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback