pushdown-automaton

Can a pushdown automata have zero final states?


As per the question, can a pushdown automata have zero final states?


Solution

  • Yep! There are many different definitions of PDAs, but usually the definition says that a PDA has a set of accepting states, which must be a subset of the set of all states in the PDA. The empty set is a valid set, so the PDA doesn't necessarily ever have to accept. This is how it's possible to build a PDA for the empty language, for example, which is known to be context-free.

    Hope this helps!