There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.

In this example it is detecting non-determinism in state q0: Non-deterministic push-down automaton

The first symbol in the transition represents the symbol read as input; the second symbol represents the symbol extracted from the stack; and the third symbol is the symbol pushed to the stack. λ represents the empty symbol, so this is an empty transition without checking the stack or pushing anything to it.

I am surprised, as that state seems to fulfill the conditions for determinism for push-down automatons (if only because it only contains a single transition!). I would expect the next state to be q1 under any circumstance.

In comparison, JFLAP doesn't find any non-determinism here: Deterministic push-down automaton

Mind you, the transition is the same, it only changes that this one adds something to the stack. Am I missing something or is JFLAP wrong in the first instance?


All deterministic push-down automatons are also nondeterministic push-down automatons, so it is correct to say that your automaton is nondeterministic.

That said you are correct in saying that your first push-down automaton is also deterministic, according to the definition on Wikipedia.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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