A Deterministic Pushdown Automaton (DPDA) is a Deterministic Finite Automaton (DFA) that also has access to a Stack, which is a Last In, First Out (LIFO) data structure.
Having access to a form of memory allows a DPDA to recognize a greater variety of strings than a DFA. For example, given a language with symbols A and B, a DFA could be constructed to recognize AB, AABB, AAABBB, but no DFA can be constructed to recognize A^nB^n for all n, whereas that is easily done with a DPDA that works as follows:
- Enter start state.
- Push
$
to the stack. - Read letter from string.
- if B, go to a terminal non-accept state.
- if A, push A on the stack, and go to state 4.
- Read a letter from string
- if A, push A on the stack and stay in this state
- if B, pop the top value from the stack.
- If the popped value is A, go to state 5.
- If the popped value is $, go to a terminal non-accept state.
- Read a letter from string
- if B, pop the top value from the stack.
- If the popped value is A, stay in this state.
- If the popped value is $, go to a terminal non-accept state.
- if we read the end of the string, pop the top value from the stack
- If the popped value is $, go to the accept state
- If the popped value is A, go to a terminal non-accept state.
- if we read anything else from the string, go to a terminal non-accept state.
- if B, pop the top value from the stack.
PDAs recognize context-free languages, with DPDAs recognizing only the deterministic subset of context-free languages. They are more powerful than DFAs in terms of the number of languages they can recognize, but less powerful than Turing Machines