Pushdown Automata
Pushdown automata are like non-deterministic finite automata, but have
an extra component called a stack.
A stack provides additional memory beyond the finite amount
available. The stack allows pushdown automata to recognize some
nonregular languages.
State a a b b
Control
A pushdown automaton (PDA) can write symbol on the stack and read
them back later.
-Writing a symbol “pushes down” all the other symbols on the stack. At
any time, the symbol on the top can be read and removed. The
remaining symbols then move back up.
-Writing a symbol on the stack is referred to as pushing the symbol,
-Removing the symbol is referred to as popping it.
A stack is a “last in, first out” storage device and read/write access can
only be done at the top.
Formal definition of a pushdown automaton:
The formal definition of a pushdown automaton is similar to that of a
finite automaton, except for the stack. The stack is a device containing
symbols drawn from some alphabet. The machine may use different
alphabets for its input and its stack. So we specify both an input
alphabet and a stack alphabet .
The transition function which describes the automaton behavior is
defined as Q x x P( Q x )
A pushdown automaton is a 6-tuple P(Q, , , , q0, F), where Q, , , ,
F are all finite sets:
1. Q is the set of states.
2. is the set of input symbols
3. is the stack alphabet
4. : Q x x P( Q x ) is the transition function
5. q0 Q is the start state and
6. F Q is the set of accept states.
Computation:
A pushdown automaton M =(Q, , , , q0, F) computes as follows:
It accepts input w if w can be written as w= w1w2…wm, where each wi
and sequences of states r0, r1, …rm Q and
strings s0, s1, …, sm * exist that satisfy the following 3 conditions.
The strings si represent the sequence of stack contents that M has on the
accepting branch of the computation:
1. r0=q0 and s0= . This condition signifies that M starts on the start state
and that the stack is empty.
2. for i=0,…., m-1, we have (ri+1,b) (ri, wi+1,a), where si=at and si+1 = bt
for some a, b and t *. This condition states that M moves
properly according to the state stack, and next input symbol.
3. rm F. This condition states that an accept state occurs at the input end.
The following is the formal description of the PDA that recognizes the
language {0n1n | n 0}.
Let M1= (Q, , , , q1, F) where
Q={q1, q2, q3, q4},
= {0, 1},
= {0, $},
F= {q1, q4}, and
is given by the following table, wherein blank entries signify
can also be defined as such:
((q1, 0, ), (q2, 0$))
((q2, 0, 0$), (q2, 0))
((q2, 0, 0), (q2, 0))
((q2, 1, 0), (q3, ))
((q3, 1, 0), (q3, ))
((q3, , $), (q4, ))
Input 0 1
Stack 0 $ 0 $ 0 $
q1 (q2,0$)
q2 (q2,0) (q3,)
q3 (q3,) (q4,)
q4
Consider the following language defined by the expression:
{anbnc2n| n ≥ 1}
(Assignment: Using Jflap design the corresponding push down
automaton)
Theorem:
A language is context free if and only if some pushdown automaton
recognizes it.
Lemma:
If a language is context free, then some pushdown automaton
recognizes it.
Let A be a Context free language; then there is a CFG G that generates
it.
PDA as a program:
We draw the program of a PDA as a flowchart. There are 5 components
to this:
A single start state
A single halt-and-accept state
A reader box: this reads one symbol from the input and,
depending on the symbol read, goes to a new state
a pop box: this pops one symbol from the stack and, depending
on the symbol , goes to a new state.
A push box: this adds a specific symbol to the stack.
The flowchart has no reject state, if the machine gets to a state and
there are no legal continuation, then we assume that the machine
halts and rejects the input.
We also need a special symbol, we will use to indicate the end of
the input string. We will also use to indicate the result of popping
when the stack is empty- we can think of this as the stack starting
with the special symbol on it.
The language {0n1n: n > 0}
START
ACCEPT
0
PUSH x READ
1 POP
1
x
POP READ
Balanced brackets:
We consider strings consisting entirely of left and right brackets. Such
strings are called balanced if (a) reading from left to right, the number
of left brackets is always at least the number of right brackets; and (b)
the total number of left brackets equals the total number of right
brackets.
A grammar for such strings is:
S (S)| SS|
Draw the flowchart for this grammar.
Nondeterministic Push down automaton:
Find a pushdown automaton that recognizes the language
{ aibjck| and i=j or i=k}
informally the PDA for this language works by first reading and
pushing the a’s. When the a’s are done, the machine has all of them in
the stack so it can match them with either the b’s or the c’s. This is
somewhat tricky because the machine does not know in advance
whether it should match the a’s with the b’s or with the c’s.
b,a
c,$
q4 q5
q0 b,a
a,a$ b,a c,a ,$
q1 q2 q3
a,aaa c,a
b,a
Input a b c
Stack a $ a $ a $ $
q0 ((q1,a$)
q1 (q1,aa) (((q2,)
q2 ((q2,) (q3,)
q3 ((q4,) (q3,) (q3,)
q4 (q4,) (q5, )
q5 (q5,) (q6,)
Informally, this PDA works by reading an a and pushing it or reading
a b and pushing it.
Given that an NPDA is in state p, with symbol A on top of the stack and
the input is symbol a, it may do one of the following:
if (p, a,A) then it :
o “pops” A from the stack
o “pushes” word A1A2…An onto the stack by starting with
symbol An, and ending with symbol A1,
o “consumes” a by moving to the next symbol to the right of
a
o enters state q
if (p, ,A)= then M does nothing.
if (p, , A) ≠ , then, without reading a , it
1. ``pops'' A off the stack,
2. ``pushes'' word A1 An onto the stack, and
3. enters state q,
as long as (q A1 An) (p , A) ;
if (p , A)= , then M does nothing.
If (q ) (p a A) , then A gets popped off, and nothing gets pushed
onto the stack.
Modes of Acceptance
A PDA is a language acceptor. We describe how words are
accepted by a PDA M . First, we start with configurations.
A configuration of M is an element of Q . For any word u ,
the configuration (q0 u $) is called the start configuration of u .
A binary relation on the set of configurations is defined as follows:
if (p u ) and (q v ) are configurations of M , then (p u ) (q v
) provided that =A and =B1 Bn , for some A B1 Bn ,
and
either u=av , and (q B1 Bn) (p a A) ,
or u=v , and (q B1 Bn) (p , A) .
Now, take the reflexive transitive closure of . When (p u ) (q v
) , we say that v is derivable from u . A word u is said to be
accepted on final state by M if (q0 u $) (q ) for some final
state q F ,
accepted on empty stack by M if (q0 u $) (q ) ,
accepted on final state and empty stack by M if (q0 u $) (q
) for some q F .
Procedure on how to convert G into an equivalent PDA, called P:
1. Place the marker symbol $ and the start variable on the stack
2. Repeat the following steps forever:
a. if the top of stack is a variable (non-terminal) symbol A, non
deterministically select one of the rules for A and substitute A by the
string on the right-hand side of the rule.
b. If the top of stack is a terminal symbol a, read the next symbol from
the input and compare it to a. If they match, pop a and repeat step 2. If
they do not match, reject on this branch of the non-determinism.
c. if the top of stack is the symbol $, enter the accept state. Doing so
accepts the input if it has all been read.
Non-Context Free languages:
The pumping lemma for context free languages states that every context
free language has a special value called the pumping length such that all
longer strings in the language can be “pumped”. This means that the
string can be divided into five parts so that the second and the fourth
parts may be repeated together.
Theorem:
Pumping lemma for context-free languages: If A is a context free
language, then there is a number p( the pumping length) where, if s is
any string in A of length at least p, then s may be divided into five
pieces s= uvxyz satisfying the conditions:
1. for each i 0, uvixyiz A
2. |vy| > 0 and
3. |vxy| p
When s is being divided into uvxyz, condition 2 says that either v or y
is not the empty string.
