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.

  • 1
    $\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 '19 at 12:17

You don't need to remove $F$ from your definition, you just don't use it in the definition for the accepted words.

Let $(p, w, \beta) \in Q \times \Sigma^* \times\Gamma^*$ be the current full state description of the PDA, where $p$ is the current state, $w$ the yet unread input and $\beta$ the current stack. The accepted language $L(M)$ then is normally defined as

$$L(M) = \{w \in \Sigma^*\mid (q_0, w, Z) \vdash^* (q, \varepsilon, \beta), q \in F, \beta \in \Gamma^*\}$$

i.e. all words that, when completely read, result after zero or more steps of the machine in a state that is in the set of final states $F$. (Definitions also vary whether your stack is empty at start or initialized with a single symbol $Z$, and whether it should be empty when the final state is reached.)

For your modified PDA you can define an L' as follows:

$$L'(M) = \{w \in \Sigma^*\mid (q_0, w, Z) \vdash^* (q, w', \varepsilon), q \in Q, w' \in \Sigma^*\}$$

The most important changes here are that the language doesn't depend on $F$ anymore and that the condition for an accepted word is a series of machine steps that leads to an empty stack.


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.