Pushdown Automata

Pushdown automata are nondeterministic finite state machines augmented with additional memory in the form of a stack, which is why the term “pushdown” is used, as elements are pushed down onto the stack. Pushdown automata are computational models—theoretical computer-like machines—that can do more than a finite state machine, but less than a Turing machine.

Pushdown automata accept context-free languages, which include the set of regular languages. The language that describes strings that have matching parentheses is a context-free language. Say that a programmer has written some code, and in order for the code to be valid, any parentheses must be matched. One way to do this would be to feed the code (as strings) into a pushdown automaton programmed with transition functions that implement the context-free grammar for the language of balanced parentheses. If the code is valid and all parentheses are matched, the pushdown automata will "accept" the code. If there are unbalanced parentheses, the pushdown automaton will be able to return to the programmer that the code is not valid. This is one of the more theoretical ideas behind computer parsers and compilers.

Pushdown automata can be useful when thinking about parser design and any area where context-free grammars are used, such as in computer language design. Since pushdown automata are equal in power to context-free languages, there are two ways of proving that a language is context-free: provide the context-free grammar or provide a pushdown automaton for the language.

\(\delta\) represents transition functions (the program of the pushdown automaton), \(A\) is the stack symbol, \(a\) is the tape symbol, and \(p\) represents the state^[1].

A stack can be thought of as a stack of plates, one stacked on top of the other, and plates can be taken off of the top of the stack. To get to the bottom of the stack of plates, all others must be removed first. Stacks are a last-in-first-out, or LIFO, data structure. In pushdown automata, state transitions include adding a symbol to the string generated, as in FSMs, but state transitions can also include instructions about pushing and popping elements to and from the stack.

One can walk through the pushdown automata diagram to see what kinds of strings can be produced by the transition functions describing the language the pushdown automata generate, or you can feed it an input string and verify that there exists a set of transitions that end in an accepting state that creates the input string.

At each transition, a pushdown automaton can push a symbol to the stack, pop a symbol from the stack, do both, or do no operations to the stack. This transition symbol is \(\epsilon\). \(\epsilon\) also represents the empty string and can be used as a symbol. If the instructions say that \(\epsilon\) is the symbol read, this means that the stack/input is empty. If the instructions say to replace the symbol on top of the stack with an \(\epsilon,\) this means to delete the symbol on top of the stack (this is popping).

The pushdown automaton starts with an empty stack and accepts if it ends in an accepting state at the end. The contents of the stack at the end do not matter unless the problem specifies that the stack must be empty at the end. If no transition from the current state can be made, reject. For example, if the transition from state A to state B requires popping an \(x\) from the stack, if there is no \(x\) on the top of the stack to pop, reject.

Pushdown automata can be modeled as a state machine diagram with added instructions about the stack. Where in the finite state machine the arrows between states were labeled with a symbol that represented the input symbol from the string, a pushdown automaton includes information in the form of input symbol followed by the symbol that is currently at the top of the stack, followed by the symbol to replace the top of the stack with. These instructions are sometimes separated by commas, slashes, or arrows:

The exception to the "replace with this symbol" command is during the first step after we write the $ symbol: we do not overwrite (i.e. pop/delete) the $ symbol. We need to keep this so that as we reach the end of the string, we know when we've reached the bottom of our stack. Instead of overwriting this symbol, simply place the next stack symbol on top of the $.

For this example, assume that \(s_5\) and \(s_6\) are the accepting states. This pushdown automaton only shows instructions for the stack; usually, the pushdown automata diagrams will also contain information about which symbols are needed to move from one state to another, but let's use this example to get a feel for how the stack works. Assume the stack starts off empty, with the symbol \($\), which indicates the bottom of the stack: so the stack is initially set to \([$]\).

^[2]

What does the stack look like after following these transitions: \(s_1\) to \(s_2\) to \(s_3\)?

Show Answer

The push down automaton pushes \(a\) and then pushes \(b,\) so the stack at this point is \([$, a, b]\).

Starting with the empty stack, what does the stack look like after the transitions \(s_1\) to \(s_2\) to \(s_3\) to \(s_3\) to \(s_4\) to \(s_4\)?

Show Answer

The push down automaton pushes \(a,\) pushes \(b,\) pushes \(b,\) pops \(b,\) and pops \(b,\) so the stack looks like \([$,a]\).

What's the point of a stack?

A stack allows pushdown automata a limited amount of memory. A pushdown automaton can read from, push (add) to, or pop (remove) the stack. The transition functions that describe the pushdown automaton (usually represented by labels on the arrows between the state circles) tell the automaton what to do.

Pushdown automata accept context-free languages. This means that a context-free language can be represented by a pushdown automaton or a context-free grammar.

For example, the language containing all strings of 0's followed by an equal number of 1's is a context-free language, and it was proved on the regular languages page that this language is not a regular language, so it is possible to represent this language using a pushdown automaton.

Here is a push down automaton that accepts strings in the language \(L = \{0,1 \big| 0^n1^n \text{ for n } \geq 0\}\).

Note: in the transition from A to B, do not overwrite the $ symbol with an empty string (i.e. don't remove the $), just write the new symbol on top of that.

A pushdown automaton is formally defined as a 7-tuple: \((Q, \Sigma, \Gamma, \delta, q_0, Z, F)\).

• \(Q\) is the finite set of states.
• \(\Sigma\) is the finite alphabet of the input alphabet.
• \(\Gamma\) is the finite stack alphabet.
• \(\delta\) is the set of transition functions.
• \(q_0\) is the starting state. This is a member of the set of states, \(Q.\)
• \(Z\) is the initial stack symbol which is a member of \(\Gamma.\)
• \(F\) is the set of accepting states which is a subset of \(Q.\)

The transition functions in \(\delta\) can be represented as another tuple: \((p, a, A, q, \alpha).\)

• \(p\) represents the current state \((\)which is a member of \(Q).\)
• \(a\) is the input \((\)in \(\Sigma \cup \epsilon)\) on which the transition is triggered.
• \(A\) is the top stack symbol \((\)which is a member of \(\Gamma)\) which may read \(a\), change the state to \(q\), pop \(A\) replacing it by pushing \(\alpha\).
• \(q\) is the state \((\)which is a member of \(Q)\) that the stack symbol might cause us to switch to.
• \(\alpha\) is the symbol \((\)which is a member of \(\Gamma)\) the stack symbol might cause us to push to the top of the stack.

Can you come up with a diagram and formal description of a pushdown automaton that recognizes strings containing only parentheses and accepts on strings that have matched parentheses? The context-free grammar for this language is here.

Show Answer

\(\Sigma = \{(,)\}\)

\(\Gamma = \{$,X\}\ \ \ \) note: the \(X\) could be any symbol you want

\(Q = \{A, B, C, D\}\)

\(F = \{D\}\)

\(q_0 = A\)

\(Z = $\)

\(\delta = \big\{(A, \epsilon, \epsilon, A, $), (A(,$,B,X), (B, (, X, B, X), (B, ), X, C, \epsilon), (C, ), X, C, \epsilon), (C, \epsilon, $, D, \epsilon)\big\}\)

We just showed that the problem above can be represented by either a context-free grammar or a pushdown automaton. Here is how to convert between the two:

Context-free grammar to pushdown automaton: ^[3]

Each derivation or sequence of production rules that results in a given string is made up of intermediate strings (which are made at each step of the derivation).

The pushdown automata's non-determinism helps it to guess the sequence of steps in the derivation that will result in the desired string. So at each step in the derivation, one of the production rules for a given variable is selected non-deterministically and substituted in for the variable.

The pushdown automaton begins by pushing a symbol onto the stack and then goes through the series of intermediate strings until it arrives at a string that contains only the terminal symbols (this will happen if the string is actually in the grammar, otherwise it will reject).

Here's what to do:

• Push the start symbol, $, to the stack.

Then the following steps are repeated until the automaton finishes:

• If there is a variable \(X\) on top of the stack, non-deterministically pick one of the production rules for \(X\) and substitute \(X\) with the string on the right-hand side of the production rule.

• If there is a terminal variable \(a\) on the input, read the next symbol from the input and compare it to \(a\). If they are the same, repeat, and if they are not, reject on this branch of the non-determinism.

• If it is the end of the input and the top of the stack has the start symbol, $, then accept.

\(\text{}\)

Pushdown automaton to context-free grammar:^[3]

The goal is to make a pushdown automaton that will accept all of the input strings that the context-free grammar accepts.

For every pair of states, \(p\) and \(q\), there will be a variable \(A_{pq}\) from the grammar. This variable will generate all of the strings that can take the pushdown automaton from state \(p\) to state \(q\).

The pushdown automaton needs to have these three features:

1. A single accepting state

2. The stack needs to be empty before it accepts.

3. Each transition must only push or pop—it can't do both or neither. To do this, to mimic a transition that does neither, we would need a transition that pushes and then another that pops, resulting in a net action of nothing done. Each of these transitions must go to a new state, so this pushdown automaton may have more states than it might need if we were converting from a context-free grammar to a pushdown automaton.

The first move on a string \(x\) must be a push since the stack starts off empty, and the last move must be a pop since the stack must be empty at the end.

There are two cases for \(x:\)

• The symbol that is popped at the end is the symbol that was pushed at the beginning. If this is the case, then we know that the stack was only ever empty at the beginning and the end. We make the production rule \(A_{pq} \rightarrow aA_{rs}b,\) where \(a\) is an input symbol, \(b\) is the symbol read at the last step, \(r\) is the state after \(p\), and \(s\) is the state preceding \(q\).

• The symbol that is popped at the end is not the symbol that was pushed at the beginning. If this is the case, then we know that the stack must have been empty sometime between the beginning and end. We make the production rule \(A_{pq} \rightarrow A_{rs}A_{rq},\) where \(a\) is an input symbol, \(r\) is the state where the stack becomes empty, and \(s\) is the state preceding \(q\).

Since pushdown automata recognize context-free languages, and context-free languages​ include regular languages, pushdown automata accept regular languages. A pushdown automaton is just a finite state machine augmented with a stack. Another way to think about this is that a finite state machine is a pushdown automaton that ignores its stack.

^[4]

If the pushdown automata had access to two stacks, making it a queue automaton, it would create a machine equal in power to a Turing machine.

• Finite State Machines

• Regular Expressions

• Regular Languages

• Context-free Languages

• Context-free Grammars

• Turing Machines

1. , J. Pushdown-overview. Retrieved June 18, 2016, from https://en.wikipedia.org/wiki/File:Pushdown-overview.svg
2. Abdulla, P., Atig, M., & Stenman, J. PDA Example. Retrieved June 18, 2016, from https://www.semanticscholar.org/paper/Adding-Time-to-Pushdown-Automata-Abdulla-Atig/1c95cfb83c281a5d443e23fc38e378aed053efba
3. Sipser, M. (1997). Introduction to the Theory of Computation (pp. 107). PWS Publishing Company.
4. Fitch, W., & Friederici , A. Artificial grammar learning meets formal language theory: an overview. Retrieved June 19, 2016, from http://rstb.royalsocietypublishing.org/content/367/1598/1933