Definition of Pushdown Automata
Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.
A Pushdown Automata (PDA) can be defined as :
- Q is the set of states
- ∑ is the set of input symbols
- Γ is the set of pushdown symbols (which can be pushed and popped from stack)
- q0 is the initial state
- Z is the initial pushdown symbol (which is initially present in stack)
- F is the set of final states
- δ is a transition function which maps Q x { ∑ ∪ ɛ } x Γ into Q x Γ *. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.
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.
A stack can be thought of as a stack of plates, one is 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, like 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 generates, 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 ɛ. ɛ also represents the empty string and can be used as a symbol. If the instructions say that ɛ 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 ɛ 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 overwritting this symbol, simply place the next stack symbol on top of the $.
For this example, assume that s5 and s6 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 [$].
What does the stack look like after following these transitions: s1 to s2 to s3 ?
The push down automaton pushes “a”, pushes “b”, and then pushes another “b” so the stack at this point is [$,a,b,b].
Starting with the empty stack, what does the stack look like after the transitions s1 to s2 to s3 to s3 to s4 to s4 ?
The push down automaton pushes “a”, pushes “b”, pushes “b”, pushes “b”, pops “b”, and pops “b”, so the stack looks like [$, a, b].
Try It Yourself:
Given the following pushdown automata and input string 00001111, what does the PDA’s stack look like once it has gotten through and read the second 1 of the string (i.e. the substring 000011 has been read).
It is easy give your answer in comments.
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, and 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 | 0^n1^n for n >= 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.