We invent a new machine:

• the pushdown automaton (PDA)
• constructed by modifying a FA as follows:

• add an arbitrary number of blank characters (called D "delta") to the end of each input
• add a push-down (LIFO) stack, initially containing a arbitrary number of D ’s
• all states will be exactly one of the following six types:

• start state: no incoming transitions. This state will transition immediately without reading any input.
• read state: reads a new character from the input, and transitions based on what was read. These states correspond to the ordinary states of an FA.
• accept state: special states, like the final states of a FA, but have no out-going transitions.
• reject state: special states that have no out-going transitions.
• push x state: pushes a character x onto the push-down stack, then transitions according to the one out-going transition.
• pop state: pops a character from the stack, and then transitions based on that character.

• the same label may appear on more than one outgoing transition (a PDA may be non-deterministic)
• similarly, the start state may transition to more than one state
• there are no l-transitions
• the machine may reach an accept state, in which case, the machine halts and input string is accepted
• the machine may reach a reject state, in which case, the machine halts and the input string is rejected
• there may be no transition specified for the character produced by a pop or read state; in such a case, the machine halts and the input string is rejected
• a PDA may accept a string without reading the whole string
• the vocabulary of characters that may appear on the stack may or may not overlap the vocabulary of characters that may appear in an input string
• on my PDA diagrams, I will designate states: S = start, A = accept, R = read, RJ = reject, P a = push a, Pop = pop
• the language defined by a PDA consists of those strings that it accepts

We only need to show that any FA can be upgraded to a PDA:

• remove l-transitions
• make each state a read state
• add a start state with a transition to the FA’s start state
• add a D -transition from each final state to an accept state
• there will, of course, be no push or pop states

Trace of our PDA's behavior on the input string aabb:

Based on this, can you tell what language this machine accepts?