# Formal definition of an empty stack accepting PDA

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.

• 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? – 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.