Deterministic Finite Automaton vs Deterministic Pushdown Automaton

Question

I was wondering if somebody could give me a simple explanation of the relationship between these two terms, as I am very confused by the terminology.

Answer 1

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:

1. Enter start state.
2. Push $ to the stack.
3. 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.
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.
5. 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.

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