PDA's are usually defined using the 7-tuple convention.

$M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$

F is the set of accepting states.

I want to design a PDA accepting by empty stack, so using this notation makes no sense, as I don't need F and I want to make the acceptance condition clear.

How is this usually done? Can I just dismiss F?

$M'=(Q, \Sigma, \Gamma, \delta, q_{0}, Z)$


When the stack is finished you can go to the specified state which shows the empty stack. In addition, when you reach in a state which you found it's a solution but the stack is not empty, iterate over a "pop" action to empty the stack and finally go the empty stack state.

Hence, you can explain this PD using the defined notation.

  • $\begingroup$ I know that empty stack and final state PDA's have the same expressive power. Yet I want to write down one automaton accepting by empty stack. E.g.: How could you formally write down an automaton for the Grammer with one production: S->a which accepts by empty stack? $\endgroup$ – PascalIv Jan 9 at 12:17

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.