2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Please don't use images as crtitical content of your post. This makes your question harder to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – D.W. ♦
    Jan 5, 2016 at 3:10

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.