Introduction to Automata Theory,

Languages, and Computation

Rikip Ginanjar
President University
Cikarang-Jawa Barat

Informatics Int. to Automata, Rikip Lecture 11, page 1

 Pushdown Automata and
Context-Free Languages

Informatics Int. to Automata, Rikip Lecture 11, page 2

 Pushdown Automata
• The context-free grammar languages have a type of automaton that defines
them: pushdown automaton
• The Pushdown automata is essentially an e-NFA with the addition of a stack.
• The stack can be read, pushed, and popped only at the top, just like the stack
data structure.
• There two versions of the pushdown automaton:
– One that accepts by entering an accepting state (like finite automata do)
– One that accepts by emptying its stack, regardless of the state it is in.
• The two variations accept exactly the context-free languages: the CFG can be
converted to equivalent pushdown automata and vice versa.
• The presence of a stack means that – unlike FA – the pushdown automaton can
“remember“ an infinite amount of information.

Informatics Int. to Automata, Rikip Lecture 11, page 3

 Informal Definition
• Let consider the language L={wwR|w in (0+1)*}. This language is the even-length
palindrome over alphabet {0,1}.
• The CFG that generates L is (Q,T,P,S) where P:
– P → e | 0P0 | 1P1
• We can design an informal pushdown automaton accepting L as follows:
– Start at state s (start state). While in s, we read symbols and store them on the stack
– At any time, we guess that we have seen the middle (end of w). At this time, w will
be on the stack, with the right end of w at the top of stack and the left end of w at
the bottom of the stack. Since the automaton is nondeterministic, we actually make
both guess: by consuming nothing we move to next state (say q) and we stay in s
and continue to read inputs, store them on the stack.
– If we are in q, we compare input symbols with the symbol at the top of the stack.
• If they match, we consume the symbol and pop the stack.
• If they do not match, we have guessed wrong. This branch dies, but other
branch may survive and eventually lead to acceptance.

Informatics Int. to Automata, Rikip Lecture 11, page 4

 Pushdown Automaton

s q
Finite Finite
input State Accept/reject input State Accept/reject
control control

push pop

stack stack

Read input symbols and Read input symbols,

push the symbols into stack compare the symbols (input and top of stack)
If matched, pop the symbols from stack

Informatics Int. to Automata, Rikip Lecture 11, page 5

 NPDAs
• A NPDA (Nondeterministic PushDown Automata) is a 7-tuple
M = (Q,S,G, d ,s, ⊥ , F) where
– Q is a finite set (the states)
– S is a finite set (the input alphabet)
– G is a finite set (the stack alphabet)
– d  (Q x (S U {e})x G) x (Q x G*) is the transition relation
– s  Q is the start state
– ⊥  G is the initial stack symbol
– F  Q is the final or accept states
• ((p,a,A),(q,B1B2…Bk))  d means that whenever the machine is in state p
reading input symbol a on the input tape and A on the top of the stack, it pops A
off the stack, push B1B2…Bk onto the stack (Bk first and B1 last), move its read
head right one cell past the a and enter state q.
• ((p,e,A),(q,B1B2…Bk))  d means similar to ((p,a,A),(q,B1B2…Bk))  d except
that it need not scan and consume any input symbol.

Informatics Int. to Automata, Rikip Lecture 11, page 6

 Configurations
• Collection of information used to record the snapshot of an executing NPDA is
an element of Q x S* x G*.
• Configuration C = (q, x, w) means
– the machine is at state q,
– the rest unread input string is x,
– the stack content is w.
• Example: the configuration (p, baaabba, ABAC⊥) might describe the situation:

A
a b a b b a a a b b a
B
A
p
C
⊥

Informatics Int. to Automata, Rikip Lecture 11, page 7

 Start configuration and the next configuration
relations
• Given a NPDA M and an input string x, the configuration (s, x, ⊥ )
is called the start configuration of NPDA on x.
• CFM =def Q x S* x G* is the set of all possible configurations for a
NPDA M.
• One-step computation of a NPDA:
– (p, ay, Ab) --> (q, y , g b) if ((p,a,A), (q, g ))  d. (1)
– (p, y, Ab) --> (q, y, g b) if ((p,e,A),(q, g ))  d . (2)
– Let the next configuration relation -->M on CFM2 be the set of pairs of
configurations satisfying (1) and (2).
– -->M describes how the machine can move from one configuration to
another in one step. (i.e., C -->M D iff D can be reached from C by
executing one instruction)
– Note: NPDA is nondeterministic in the sense that for each C there may exist
multiple D’s s.t. C -->M D.
Informatics Int. to Automata, Rikip Lecture 11, page 8
 Multi-step computations and acceptance
• Given a next configuration relation -->M:
Define --->nM and --->*M as usual, i.e.,
– C -->0M D iff C = D.
– C -->n+1M D iff $ E C-->n M E and E-->M D.
– C -->*M D iff $ n  0 C -->nM D.
– i.e., --->*M is the ref. and trans. closure of --> M .
• Acceptance: When will we say that an input string x is accepted by an NPDA M?
– two possible answers:
– 1. by final states: M accepts x ( by final state) iff
– (s,x, ⊥ ) -->*M (p,e, a) for some final state p  F.
– 2. by empty stack: M accepts x by empty stack iff
– (s,x, ⊥) -->*M (p,e, e) for any state p.
– Remark: both kinds of acceptance have the same expressive power.

Informatics Int. to Automata, Rikip Lecture 11, page 9

 Language accepted by a NPDAs

M = (Q,S,G,d,s,,F) : a NPDA.
The languages accepted by M is defined as follows:
– 1. accepted by final state:
– Lf(M) = {x | M accepts x by final state}
– 2. accepted by empty stack:
– Le(M) = {x | M accepts x by empty stack}.
– 3. Note: Depending on the context, we may sometimes use Lf
and sometimes use Le as the official definition of the language
accepted by a NPDA. I.e., if there is no worry of confusion,
we use L(M) instead of Le(M) or Lf(M) to denote the language
accepted by M.
– 4. In general Le(M)  Lf(M).
Informatics Int. to Automata, Rikip Lecture 11, page 10
 Some example NPDAs
M1: A NPDA accepting the set of balanced strings of parentheses [ ] by empty stack.
– M1 requires only one state q and behaves as follows:
1. while input is ‘[‘ : push ‘[‘ onto the stack ;
2. while input is ‘]’ and top is ‘[’ : pop
3. while input is ‘e’ and top is ⊥ : pop.
Formal definition: Q = {q}, S = {[,]}, G = {[, ⊥ },
start state = q, initial stack symbol = ⊥.
d = { ( (q,[, ⊥), (q, [⊥) ), ( (q,[, [), (q, [[) ), ( (q,], [), (q, e) ), ( (q,e, ⊥), (q, e) ) }

• This machine is not deterministic. Why ?

Informatics Int. to Automata, Rikip Lecture 11, page 11

 Example execution sequences of M1:
• let input x = [ [ [ ] ] [ ] ] [ ]. Then below is a successful computation of M1 on
x:
• (q, [ [ [ ] ] [ ] ] [ ], ⊥) : the start configuration
-->M (q, [ [ ] ] [ ] ] [ ], [ ⊥) instruction or transition (i)
-->M (q, [ ] ] [ ] ] [ ], [ [ ⊥) transition (ii)
-->M (q, ] ] [ ] ] [ ], [ [ [ ⊥) transition (ii)
-->M (q, ] [ ] ] [ ], [ [ ⊥) transition (iii)
-->M (q, [ ] ] [ ], [⊥) transition (iii)
-->M (q, ] ] [ ], [ [ ⊥) transition (ii)
-->M (q, ] [ ], [ ⊥) transition (iii)
-->M (q, [ ], ⊥) transition (iii)
-->M (q, ], [ ⊥) transition (i)
-->M (q, , ⊥) transition (iii)
-->M (q, , ) transition (iv)
accepts by empty stack
Informatics Int. to Automata, Rikip Lecture 11, page 12
 Failure computation of M1 on x

• Note besides the above successful computation, there are other computations
that fail.
Ex: (q, [ [ [ ] ] [ ] ] [ ], ⊥) : the start configuration
-->*M (q, [ ], ⊥)
-->M (q, [ ], ) transition (iv)
• a dead state at which the input is not empty and we cannot move further =>
failure!!
• Note: For a NPDA to accept a string x, we need only one successful
computation (i.e., $ D with empty input and stack s.t. (s,x,⊥) -->*M D. )
• One guess ends with failure, but other guess will eventually get to the
final/empty stack.

Informatics Int. to Automata, Rikip Lecture 11, page 13

 Another example

• From previous slide (page 4), The grammar that generates this
language L= {wwR | w  {a,b}*} was given.
• The design of PDA that accept the language L is as follows:
• P = ({q0,q1,q2}, {0,1}, {0,1, ⊥}, d, q0, ⊥,{q2}) where d is defined
by the following rules:
– d(q0,0, ⊥)= {(q0,0 ⊥)} and d(q0,1, ⊥)= {(q0,1 ⊥)}
– d(q0,0,0)= {(q0,00)}, d(q0,0,1)={(q0,01)}, d(q0,1,0)={(q0,1,0)},
d(q0,1,1)={(q0,11)}
– d(q0,e, ⊥)= {(q1, ⊥)}, d(q0,e,0) ={(q1,0)}, d(q0,e,1)={(q1,1)}
– d(q1,0,0)={(q1,e)}, d(q1,1,1)={(q1,e)}
– d(q1,e, ⊥)={(q2, ⊥)}

Informatics Int. to Automata, Rikip Lecture 11, page 14

 Graphical Notation

0, ⊥/0⊥
1, ⊥/1⊥
0,0/00
0,1/01
1,0/10 0,0/e
1,1/11 1,1/e

q0 q1 q2
e, ⊥/⊥ e, ⊥/⊥
e,0/0
e,1/1

Informatics Int. to Automata, Rikip Lecture 11, page 15