Theory of Computation

Link to Lectures

Instructor: Prof. Michael Sipser

Book: “Introduction to the Theory of Computation” by Michael Sipser

ROUGH NOTES (!)
Updated: 8/2/24

Lec-1:

Computability Theory (1930s - 50s): What is computable or not ?

Eg: Program verification, Pure mathematical truth
Models of computation: Finite automata, Turing machines

Complexity Theory (1960s - Present): What is computable in practice ?

Eg: Factoring problem, in fact P vs NP problem
Measures of complexity: Time and Space

P vs NP is a millennium prize problem. Geometric Complexity Theory is a research program aimed at resolving this is.

A finite automaton is a ${ 5 - }$tuple ${ (Q, \Sigma, \delta, q _0, F) }$ where:

${ Q }$ is a finite set of states
${ \Sigma }$ is a finite set of alphabet symbols
${ \delta }$ is a transition function ${ \delta : Q \times \Sigma \to Q }$
${ q _0 \in Q }$ is the start state
${ F \subseteq Q }$ is the set of final/accept states.

A string is a finite sequence of symbols in ${ \Sigma }.$ A language is a (finite or infinite) set of strings.
The empty string ${ \varepsilon }$ is the string of length ${ 0 .}$ The empty language ${ \emptyset }$ is the language with no strings.

Finite automaton ${ M }$ accepts string ${ w = w _1 \ldots w _n }$ (each ${ w _i \in \Sigma }$) if there is a sequence of states ${ r _0, r _1, \ldots, r _n \in Q }$ such that:

${ r _0 = q _0 }$
${ r _i = \delta (r _{i-1}, w _i) }$ for ${ 1 \leq i \leq n }$
${ r _n \in F .}$

For a finite automaton ${ M ,}$ the language ${ L(M) = \lbrace w \vert M \text{ accepts } w \rbrace }$ is called the language of ${ M .}$ (We also say ${ M }$ recognizes ${ L(M) }$).
A language is called regular if some finite automaton recognizes it.

Goal: Understand the regular languages.

Eg: The language ${ \lbrace w \in \lbrace 0,1 \rbrace ^{*} \vert w \text{ contains substring } 11 \rbrace }$ is regular. (Language of the automaton here at 30:00).
The language ${ \lbrace w \vert w \text{ has equal number of } 0s \text{ and } 1s \rbrace }$ is not regular (will show later).

Operations on languages:
Let ${ A, B }$ be languages. Then we have languages:

Union ${ A \cup B }$ ${ = \lbrace w \vert w \in A \text{ or } w \in B \rbrace }$
Concatenation ${ AB }$ ${ = \lbrace xy \vert x \in A \text{ and } y \in B \rbrace }$
Star ${ A ^{*} }$ ${ = \lbrace x _1 \ldots x _{k} \vert \text{each } x _i \in A \text{ for } k \geq 0 \rbrace }$ (Note empty string ${ \varepsilon \in A ^{*} }$ always).

We say ${ R }$ is a regular expression if ${ R }$ is:

${ a }$ for some ${ a \in \Sigma }$
${ \varepsilon }$
${ \emptyset }$
${ R _1 \cup R _2 }$ where ${ R _1, R _2 }$ are regular expressions
${ (R _1 \circ R _2) }$ where ${ R _1, R _2 }$ are regular expressions
${ R _1 ^{*} }$ where ${ R _1 }$ is a regular expression.

Informally, regular expressions are built from elements of ${ \Sigma ,}$ empty string ${ \varepsilon ,}$ empty set ${ \emptyset ,}$ and finite union, concatenation, star operations.

Eg: Say ${ \Sigma = \lbrace 0, 1 \rbrace. }$ Expression ${ (0 \cup 1) ^{*} = \Sigma ^{*} }$ gives all strings over ${ \Sigma = \lbrace 0, 1 \rbrace }.$ Expression ${ \Sigma ^{*} 1 }$ gives all strings that end in ${ 1 }.$ Expression ${ \Sigma ^{*} 1 1 \Sigma ^{*} }$ gives all strings that contain ${ 1 1 .}$ (These are regular languages, not a coincidence).

Goal: Show finite automata are equivalent to regular expressions.

We’ll show regular languages are closed under finite ${ \cup },$ ${ \circ }$ and ${ (\cdots) ^{*}. }$

Thm: If ${ A _1, A _2 }$ are regular languages, so is ${ A _1 \cup A _2 }.$
Sketch: Say ${ M _1 }$ ${ = (Q _1, \Sigma, \delta _1, q _1, F _1 ) }$ recognises ${ A _1 }$ and ${ M _2 = }$ ${ (Q _2, \Sigma, \delta _2, q _2, F _2) }$ recognises ${ A _2 }.$ Consider ${ M = (Q, \Sigma, \delta, q _0, F) }$ with states ${ Q = Q _1 \times Q _2 },$ transition function ${ \delta((r _1, r _2), a) = (\delta _1 (r _1, a), \delta _2 (r _2, a)), }$ start state ${ q _0 = (q _1, q _2) }$ and accept states ${ F = (F _1 \times Q _2) \cup (Q _1 \times F _2) }.$ The automaton ${ M }$ recognises ${ A _1 \cup A _2 }.$

Lec-2:

Goal: Show finite automata are equivalent to regular expressions.

Thm: If ${ A _1, A _2 }$ are regular languages, so is ${ A _1 A _2 .}$
Sketch: Say finite automaton ${ M _1 }$ recognises ${ A _1 ,}$ and ${ M _2 }$ recognises ${ A _2 }.$ Attempting to connect accept states of ${ M _1 }$ to start state of ${ M _2 }$ doesn’t really work. Needs a new concept, Non-determinism.

Features of non-determinism:

Multiple paths possible (${ 0 },$ ${ 1 }$ or many choices at each step)
An ${ \varepsilon -}$transition is a “free move” without reading any symbol
Accept input if some path leads to an accept state.

Non-determinism doesn’t correspond to a physical machine that can be built, but is useful mathematically.

A nondeterministic finite automaton (NFA) is a ${ 5 - }$tuple ${ (Q, \Sigma, \delta, q _0, F) },$ with everything same as a finite automaton except the transition function being ${ \delta : Q \times \Sigma _{\varepsilon} \to \mathcal{P}(Q) }$ (where ${ \Sigma _{\varepsilon} = \Sigma \cup \lbrace \varepsilon \rbrace }$).

The notion of accepting a string is modified accordingly. An NFA ${ N = (Q, \Sigma, \delta, q _0, F) }$ accepts string ${ w = w _1 \ldots w _n }$ (each ${ w _i \in \Sigma _{\varepsilon} }$) if there is a sequence of states ${ r _0, \ldots, r _n \in Q }$ such that:

${ r _0 = q _0 }$
${ r _i \in \delta(r _{i-1}, w _i) }$ for ${ 1 \leq i \leq n }$
${ r _n \in F }.$

Thm [Converting NFAs to DFAs]:
If an NFA recognises ${ A }$ then ${ A }$ is regular.
Sketch: Say ${ N = (Q, \Sigma , \delta, q _0, F) }$ is an NFA recognizing ${ A. }$ We want a DFA ${ M = (Q ^{‘}, \Sigma, \delta ^{‘}, q _0 ^{‘}, F ^{‘}) }$ that recognizes ${ A .}$
Say the states of DFA are ${ Q ^{‘} = \mathcal{P}(Q) }.$ Given a state ${ R \in Q ^{‘} ,}$ we can consider its ${ \varepsilon-}$expansion (although the DFA should have no ${ \varepsilon -}$transitions) to be ${ E(R) = \lbrace q \in Q \vert q \text{ can be reached from } R \text{ by going along } 0 \text{ or more } \varepsilon \text{-arrows} \rbrace .}$ Say the start state of DFA is ${ E(\lbrace q _0 \rbrace) }.$ To construct the transition function of the DFA… first consider ${ \hat{\delta} : Q ^{‘} \times \Sigma \to Q ^{‘} }$ where ${ \hat{\delta}(R, a) = \cup _{r \in R} \delta(r, a) }$ (That is, all points of NFA that can be reached by starting at an ${ r \in R }$ and reading the symbol ${ a (\neq \varepsilon) \in \Sigma }$). Now the actual transition function of DFA is ${ \delta ^{‘} : Q ^{‘} \times \Sigma \to Q ^{‘} }$ where ${ \delta ^{‘} (R, a) = E( \hat{\delta}(E(R), a)) .}$ That is, to read a symbol ${ a \in \Sigma, }$ expand the state, read ${ a }$ in the sense of ${ \hat{\delta} ,}$ and expand the result. Say the accept states of DFA are ${ F ^{‘} = \lbrace R \in Q ^{‘} \vert R \text{ contains an accept state of NFA } N \rbrace .}$
We see this DFA ${ M }$ recognises the same language as the NFA ${ N }$. (At every step in the computation of ${ M }$ on an input, it enters a state corresponding to the subset of states that ${ N }$ could be in at that point).

That regular languages are closed under (finite) union can be proved again using NFAs.

Thm: If ${ A _1, A _2 }$ are regular languages so is ${ A _1 \cup A _2 .}$
Sketch: Say DFAs ${ M _1 }$ and ${ M _2 }$ recognize ${ A _1 }$ and ${ A _2 }$ respectively. It suffices to construct an NFA recognizing ${ A _1 \cup A _2 .}$ For the NFA: put the DFAs ${ M _1, M _2 }$ side by side, add a new start state, add ${ \varepsilon-}$transitions from the new start state to the start states of ${ M _1 }$ and ${ M _2 }.$ Remove start labels of ${ M _1, M _2 .}$ This NFA recognizes ${ A _1 \cup A _2 .}$

Thm: If ${ A _1, A _2 }$ are regular languages so is ${ A _1 A _2. }$
Sketch: Say DFAs ${ M _1 }$ and ${ M _2 }$ recognize ${ A _1 }$ and ${ A _2 }$ respectively. It suffices to construct an NFA recognizing ${ A _1 A _2 .}$ For the NFA: put the DFAs ${ M _1, M _2 }$ one after the other, add ${ \varepsilon -}$transitions from accept states of ${ M _1 }$ to start state of ${ M _2 .}$ Remove the accept labels of ${ M _1 }$ and start label of ${ M _2 .}$ This NFA recognizes ${ A _1 A _2 .}$

Thm: If ${ A }$ is a regular language, so is ${ A ^{*} .}$
Sketch: Say DFA ${ M }$ recognizes ${ A .}$ It suffices to construct an NFA recognizing ${ A ^{*} .}$ For the NFA: add ${ \varepsilon-}$transitions from accept states to the start state, add a new start state and an ${ \varepsilon-}$transition from new start state to old start state. Remove start label from old start state, and add accept label to new start state. This NFA recognizes ${ A ^{*} .}$

Thm: If ${ R }$ is a regular expression and ${ A = L(R), }$ then ${ A }$ is regular.
Sketch: (Lecture at 56:00) The NFA which recognizes ${ A }$ follows from above closure constructions.

Lec-3:

We will show: If ${ A }$ is regular then ${ A = L(R) }$ for some regular expression ${ R .}$ (That is, regular languages are equivalent to regular expressions).

A generalized NFA (GNFA) is similar to an NFA, but allows regular expressions as transition labels.

For convenience, we require that GNFAs always have a special form:

The start state has arrows going out to every other state but no arrows coming in from any other state.
There is a single accept state, and it has arrows coming in from every other state but no arrows going out to any other state.
Accept state and start state are different.
Except for the start and accept states, one arrow goes from every state to every other state and also from each state to itself.

So formally, a generalized NFA (GNFA) is a ${5-}$tuple ${ (Q, \Sigma, \delta, q _{\text{start}}, q _{\text{accept}}) }$ where:

${ Q }$ is the finite set of states
${ \Sigma }$ is the input alphabet
${ \delta : (Q - \lbrace q _{\text{accept}} \rbrace) \times (Q - \lbrace q _{\text{start}} \rbrace) \longrightarrow \mathcal{R}, }$ where ${ \mathcal{R} }$ is the set of all regular expressions over ${ \Sigma ,}$ is the transition function
${ q _{\text{start}} }$ is the start state
${ q _{\text{accept}} }$ is the accept state.

A GNFA accepts a string ${ w \in \Sigma ^{*} }$ if there is a decomposition ${ w = w _1 \ldots w _k }$ (each ${ w _i \in \Sigma ^{*} }$) and a sequence of states ${ q _0, q _1, \ldots, q _k }$ such that:

${ q _0 = q _{\text{start}} }$ is the start state
${ q _k = q _{\text{accept}} }$ is the accept state
For each ${ i , }$ ${ w _i \in L(R _i) }$ where ${ R _i = \delta(q _{i-1}, q _i) .}$

We can easily convert a DFA to a GNFA in special form:

Add a new start state with an ${ \varepsilon -}$arrow to old start state. Add a new accept state with ${ \varepsilon -}$arrows from old accept states. Remove old start and accept labels.
If there are multiple arrows from one state to another, replace with a single arrow having union of previous labels. Add arrows labelled ${ \emptyset }$ between states that had no arrows.

We can convert a GNFA into a regular expression.
Sketch: Say the GNFA has ${ k }$ states. Since there are atleast the start and accept states, ${ k \geq 2 .}$ If ${ k > 2 }$ we will construct an equivalent GNFA with ${ k-1 }$ states. (Continuing so, if ${ k = 2 }$ the GNFA has a single arrow from the start state to accept state. The label of this arrow is the equivalent regular expression). The removal of one state is done as follows:
As ${ k > 2 }$ pick a state ${ q _{\text{rip}} \in Q }$ different from ${ q _{\text{start}} }$ and ${ q _{\text{accept}} }.$ We rip out ${ q _{\text{rip}}, }$ and repair the remainder so that the same language is still recognized. In the old machine, if we had arrows ${ q _i \overset{R _1}{\longrightarrow} q _{\text{rip}} ;}$ ${ q _{\text{rip}} \overset{R _2}{\longrightarrow} q _{\text{rip}} ;}$ ${ q _{\text{rip}} \overset{R _3}{\longrightarrow} q _j }$ and ${ q _i \overset{R _4}{\longrightarrow} q _j ,}$ then in the new machine the arrow from ${ q _i }$ to ${ q _j }$ gets the label ${ R _1 R _2 ^{*} R _3 \cup R _4 .}$ We make this change for each arrow going from any state ${ q _i }$ to any state ${ q _j }$ (including the case ${ q _i = q _j }$). The new machine now recognizes the original language.

Pumping lemma helps see if a language is non-regular.

Pumping lemma: For every regular language ${ A ,}$ there is a number ${ p }$ (called “pumping length”) such that if ${ s \in A }$ and ${ \vert s \vert \geq p }$ then ${ s = xyz }$ where

${ x y ^{i} z \in A }$ for all ${ i \geq 0 }$ (this is the pumping part)
${ y \neq \varepsilon }$
${ \vert xy \vert \leq p .}$

Informally: ${ A }$ is regular ${ \implies }$ every long string in ${ A }$ can be pumped and the result stays in ${ A .}$

Sketch: Let DFA ${ M = (Q, \Sigma, \delta, q _1, F) }$ recognize ${ A .}$ Set ${ p = \vert Q \vert, }$ the number of states in ${ M .}$
Now consider any string ${ s = s _1 \ldots s _n \in A }$ of length ${ n \geq p .}$ On processing string ${ s ,}$ say ${ M }$ enters the sequence of states ${ r _1 \overset{s _1}{\longrightarrow} r _2 \longrightarrow \ldots \longrightarrow r _n \overset{s _n}{\longrightarrow} r _{n+1} .}$ The sequence of states ${ r _1 \ldots r _{n+1} }$ has length ${ n + 1 \geq p + 1 ,}$ and there are ${ p }$ distinct states in ${ M .}$ So some ${ r _j = r _l }$ with ${ j < l \leq p + 1 .}$
Now ${ r _1 \overset{s _1 \ldots s _{j-1}}{\longrightarrow} r _{j} \overset{s _j \ldots s _{l-1}}{\longrightarrow} r _l (= r _j) \overset{s _l \ldots s _n}{\longrightarrow} r _{n+1} .}$ So writing the string ${ s = s _1 \ldots s _n }$ as ${ s = \underbrace{s _1 \ldots s _{j-1}} _{x} \, \underbrace{s _j \ldots s _{l -1} } _{y} \underbrace{s _l \ldots s _n} _{z} }$ gives the required decomposition:

${ x y ^{i} z \in A }$ for all ${ i \geq 0 }$
${ y \neq \varepsilon, }$ as ${ j < l }$
${ \vert xy \vert \leq p ,}$ as ${ l \leq p + 1 .}$

Eg: The language ${ D = \lbrace 0 ^k 1 ^k \vert k \geq 0 \rbrace }$ is not regular.
Sketch: Say the language ${ D }$ were regular. Then there is a pumping length ${ p .}$ Now consider the string ${ s = 0 ^p 1 ^p \in D.}$
Pumping lemma says we can write ${ s }$ as ${ s = xyz }$ with properties as above. As ${ \vert xy \vert \leq p ,}$ substring ${ xy }$ is just ${ 0 }$s (and ${ y \neq \varepsilon }$). But now ${ x y ^{2} z }$ has more ${ 0 }$s than ${ 1 }$s, so ${ x y ^{2} z \notin D ,}$ a contradiction.
Hence ${ D }$ is not regular.

Eg: Consider ${ F = \lbrace w ^2 \vert w \in \Sigma ^{*} \rbrace }$ with ${ \Sigma = \lbrace 0, 1 \rbrace .}$ The language ${ F }$ is not regular.
Sketch: Say the language ${ F }$ were regular. Then there is a pumping length ${ p .}$ Now consider the string ${ s = 0 ^p 1 0 ^p 1 \in F . }$
Pumping lemma says we can write ${ s }$ as ${ s = xyz }$ with properties as above. As ${ \vert xy \vert \leq p, }$ the substring ${ xy }$ is just ${ 0 }$s (and ${ y \neq \varepsilon }$). Now ${ \underbrace{xy ^2} _{\text{just } 0s} z \notin F ,}$ a contradiction.
Hence ${ F }$ is not regular.

Eg: Consider ${ B = \lbrace w \vert w \text{ has equal number of } 0s \text{ and } 1s \rbrace }$ over symbols ${ \Sigma = \lbrace 0, 1 \rbrace .}$ The language ${ B }$ is not regular.
Sketch: Say the language ${ B }$ were regular. Now ${ B \cap 0 ^{*} 1 ^{*} = \lbrace 0 ^k 1 ^k \vert k \geq 0 \rbrace }$ is regular. But we already showed ${ \lbrace 0 ^k 1 ^k \vert k \geq 0 \rbrace }$ is not regular, a contradiction.
Hence ${ B }$ is not regular.

Lec-4:

An example of a context free grammar (CFG) is ${ G _1 }$ given by:

\[{ S \to 0S1 }\] \[{ S \to R }\] \[{ R \to \varepsilon. }\]

A grammar consists of a collection of substitution rules. Each rule appears as a line, comprising of a symbol and a string separated by an arrow. Here the symbol is called a variable. The string consists of variables and other symbols called terminals. The top left variable is the start variable.

A CFG describes a language by generating each string of that language as follows:

Write down the start variable (i.e. top left variable).
Find a variable that is written down and a rule which starts with that variable. Replace the written down variable with right hand side of that rule.
Repeat above step until no variables remain.

The sequence of substitutions to obtain a string is called a derivation. For example, grammar ${ G _1 }$ generates the string ${ 000\varepsilon 111 },$ and a derivation is ${ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 000R111 \Rightarrow 000\varepsilon 111.}$

All strings a grammar generates form the language of the grammar. Here, language of the grammar ${ G _1 }$ is ${ L(G _1) = \lbrace 0 ^n 1 ^n \vert n \geq 0 \rbrace. }$

Also, we abbreviate rules with same left hand variable, for eg ${ S \to 0S1 }$ and ${ S \to R },$ as ${ S \to 0S1 \vert R .}$

Repeating the above with formalism:

A context free grammar (CFG) ${ G }$ is a ${ 4-}$tuple ${ (V, \Sigma, R, S) }$ where:

${ V }$ is a finite set of variables.
${ \Sigma }$ is a finite set of terminal symbols.
${ R }$ is a finite set of substitution rules (rule form: ${ V \to (V \cup \Sigma) ^{*} }$).
${ S \in V }$ is the start variable.

For ${ u, v \in (V \cup \Sigma) ^{*} }$ write:

${ u \Rightarrow v }$ if we can go from ${ u }$ to ${ v }$ in one substitution step.
${ u \overset{*}{\Rightarrow} v }$ if we can go from ${ u }$ to ${ v }$ in some number of substitution steps in ${ G .}$ We call ${ u \Rightarrow u _1 \Rightarrow \ldots \Rightarrow u _{k} = v }$ a derivation of ${ v }$ from ${ u .}$

We can also draw a parse tree for generation of a string (ref: lecture at 16:00). The language of the grammar ${ G }$ is ${ L(G) = \lbrace w \in \Sigma ^{*} \vert S \overset{*}{\Rightarrow} w \rbrace.}$ Language generated by a context free grammar is called a context free language (CFL).

Later (?): Relation between how compilers parse code and context free grammars.

If a string has two different parse trees then it is derived ambiguously and we say the grammar is ambiguous.

Eg: The grammar given by ${ E \to E + E \vert E \times E \vert (E) \vert a }$ is ambiguous (see the lecture at 25:00).

A pushdown automaton (PDA) reads strings like NFAs, but has an extra component called a stack. There is both a tape containing the input string and a stack. A PDA can write and push a symbol to the stack (all other symbols get pushed down), or read and pop a symbol from the stack (all other symbols get pulled up). Especially stack is a “last in first out” infinite storage device: If certain information is written on the stack and additional information is written afterward, the earlier information becomes inaccessible until the later information is removed.

The formal definition of a PDA is similar to that of an NFA, except for the stack. Consider input alphabet ${ \Sigma }$ and stack alphabet ${ \Gamma .}$
The transition function has domain ${ Q \times \Sigma _{\varepsilon} \times \Gamma _{\varepsilon} }$: it takes as input a state, an input symbol (including ${ \varepsilon }$, equivalent to not reading any input) and a stack symbol (including ${ \varepsilon }$, equivalent to not reading any stack symbol). The transition function nondeterministically returns a value in ${ Q \times \Gamma _{\varepsilon} ,}$ i.e. the machine enters a state and writes a symbol (including ${ \varepsilon }$, equivalent to not writing any stack symbol) on top of the stack. So the transition function is modelled by ${ \delta : Q \times \Sigma _{\varepsilon} \times \Gamma _{\varepsilon} \longrightarrow \mathcal{P}(Q \times \Gamma _{\varepsilon}) .}$
We haven’t yet captured how the stack moves on read-pop and write-push. We will do that when discussing how a PDA processes an input string.

A pushdown automaton (PDA) is a ${ 6-}$tuple ${ (Q, \Sigma, \Gamma, \delta, q _0, F) }$ where:

${ Q }$ is a finite set of states.
${ \Sigma }$ is the finite set of input alphabets.
${ \Gamma }$ is the finite set of stack alphabets.
${ \delta : Q \times \Sigma _{\varepsilon} \times \Gamma _{\varepsilon} \longrightarrow \mathcal{P}(Q \times \Gamma _{\varepsilon}) }$ is the transition function.
${ q _0 \in Q }$ is the start state.
${ F \subseteq Q }$ is the set of accepting states.

A PDA ${ M = (Q, \Sigma, \Gamma, \delta, q _0, F) }$ computes as follows. It accepts input string ${ w }$ if it can be written as ${ w = w _1 \ldots w _m }$ (each ${ w _m \in \Sigma _{\varepsilon} }$) and there exist a sequence of states ${ r _0, r _1, \ldots, r _m \in Q }$ and sequence of strings ${ s _0, s _1, \ldots, s _m \in \Gamma ^{*} }$ (here ${ s _i }$ denotes the stack contents at stage ${ i }$) such that:

${ r _0 = q _0 }$ and ${ s _0 = \varepsilon }$ (This signifies that ${ M }$ starts out properly, in the start state and with an empty stack).
For ${ i = 0, 1, \ldots, m-1 ,}$ we have ${ (r _{i+1}, b) \in \delta(r _i, w _{i+1}, a) }$ where ${ s _i = at }$ and ${ s _{i+1} = bt }$ for some ${ a , b \in \Gamma _{\varepsilon} }$ and ${ t \in \Gamma ^{*} .}$

Saying ${ (r _{i+1}, b) \in \delta(r _i, w _{i+1}, a) }$ means the machine, in state ${ r _i }$ on reading ${ w _{i+1} \in \Sigma _{\varepsilon} }$ from tape and read-popping ${ a \in \Gamma _{\varepsilon} }$ from stack, moved to state ${ r _{i+1} }$ and write-pushed ${ b \in \Gamma _{\varepsilon} }$ to the stack. In this, initially the stack contents look like ${ s _i = at, t \in \Gamma ^{*} }$ and the new stack contents are ${ s _{i+1} = bt .}$
${ r _m \in F ,}$ that is an accept state occurs at the end.

Eg: Consider the following PDA:

In the diagram, an arrow “${ a, b \to c }$” means the machine reads input ${ a ,}$ read-pops ${ b }$ and write-pushes ${ c }$ in that process.
We see the above PDA is ${ M = (Q, \Sigma, \Gamma, \delta, q _1, F) }$ where states are ${ Q = \lbrace q _1, q _2, q _3, q _4 \rbrace ,}$ tape symbols are ${ \Sigma = \lbrace 0,1 \rbrace, }$ stack symbols are ${ \Gamma = \lbrace 0, $ \rbrace }$ and accept states are ${ F = \lbrace q _1, q _4 \rbrace .}$

In the above example, we can think of ${ 0 }$ as being the only stack symbol, and that ${ $ }$ was used just to “signal an empty stack”. The formal definition of a PDA has no explicit mechanism to allow the PDA to test for an empty stack. Above PDA brings the same effect, by initially placing a ${ $ }$ on the stack, and then if it ever sees a ${ $ }$ again the stack is effectively empty (and the PDA reaches an accept state on read-popping the ${ $ }$).

Eg: For a string ${ w = w _1 \ldots w _n }$ in ${ \lbrace 0, 1 \rbrace ^{*} }$ it’s reverse string is ${ w ^{\mathcal{R}} = w _n \ldots w _1. }$ Here is a PDA recognizing ${ \lbrace w w ^{\mathcal{R}} : w \in \lbrace 0, 1 \rbrace ^{*} \rbrace }$ :

As in the above example, the ${ $ }$ technique is used to detect an empty stack. Informally the machine processes input strings as:

Begin by pushing symbols that are read onto the stack (The “${ q _2 }$ phase”).
At each point, nondeterministically guess the middle of the string has been reached, and change off to popping off the stack for each symbol read (i.e. switch to the “${ q _3 }$ phase”).
If the input string ends and stack empties (i.e. stack becomes ${ $ }$) at the same time, we can reach the accept state.

Goal: Constructively show that a language is context free if and only if some pushdown automaton recognizes it.

Thm: If a language is context free, then some pushdown automaton recognizes it.
Sketch: Let ${ L }$ be a CFL. So there is a CFG ${ G }$ generating ${ L .}$ We now want a PDA ${ P }$ recognizing ${ L .}$
First, consider the following shorthand in drawing a PDA. In a regular PDA diagram, an arrow between states ${ q \overset{a, s \to u}{\longrightarrow} r }$ means ${ (r, u) \in \delta(q, a, s) ,}$ that is when the machine is in state ${ q }$ and follows this arrow: it reads input symbol ${ a \in \Sigma _{\varepsilon}, }$ read-pops symbol ${ s \in \Gamma _{\varepsilon} ,}$ and write-pushes symbol ${ u \in \Gamma _{\varepsilon} ,}$ moves to state ${ r.}$ In the new PDA convention, an arrow between states ${ q \overset{a, s \to u _1 \ldots u _n}{\longrightarrow} r }$ amounts to having new states and arrows ${ q \overset{a, s \to u _n}{\longrightarrow} q _1 \overset{\varepsilon, \varepsilon \to u _{n-1}}{\longrightarrow} \ldots \longrightarrow q _{n-1} \overset{\varepsilon, \varepsilon \to u _1}{\longrightarrow} r .}$
On starting at state ${ q }$ and following the arrow(s), the machine: reads symbol ${ a \in \Sigma _{\varepsilon} },$ read-pops ${ s \in \Gamma _{\varepsilon} ,}$ and write-pushes ${ u _1 \ldots u _n }$ onto the stack, moves to state ${ r .}$ The shorthand is described, for ${ n = 3,}$ by the following diagram.