Sipser: Section 2.2

From CSWiki

Jump to: navigation, search

CSC 341: Front Door

CSC 341: Cooperative commentary | Sipser:_Chapter_2

[edit]

Defining Pushdown Automata

A pushdown automaton is similar to the Finite State machines we've discussed so far with the exception that a pushdown automaton maintains a single, unbound stack.
This stack allows a pushdown automaton to recognize some nonregular languages.
States - $Q$ , Input alphabet - $Σ$ , Start state - $q_0 \in Q$ , and accept state - $F$ remain unchanged from Finite State machines. We also include $Γ$ , the stack alphabet, as well as modify $δ$ so that it makes decisions based on the top of the stack. $δ$ now represents the transitions from $Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \rightarrow P(Q \times \Gamma_\varepsilon)$
Pushdown Automata is 6-tuple.

[edit]

State Diagram

Transitions in a Pushdown Automaton's state diagram follow the form " $a,b\rightarrow c$ ", where $a$ is the input character, $b$ is the character that was at the top of the stack (will be removed), and $c$ is the character that will replace $b$ on the stack.

If $a=\varepsilon$ , no input is required to change the stack and state
If $b=\varepsilon$ , the top of the stack is not removed; this allows us to add on to the stack without removing elements
If $c=\varepsilon$ , no symbol is written to the stack; this allows us to remove the top of the stack without replacing it