Chapter 4.

Push down automata

4.1. Non-deterministic pushdown automata

4.2. Pushdown automata and Context Free Languages

4.3. Deterministic pushdown automata

4.4. Deterministic Context Free Languages

1
 Push down automata (PDA)

• A pushdown automaton is a type of finite automaton that uses a stack to

recognize Context Free Languages.

• It reads a given input string from left to right and chooses a transition by
indexing a table by input symbol, current state, and the symbol at the top
of the stack.

• It has a transition function that maps the current state, input symbol, and
stack symbol to a new state and stack symbol.
2
 Cont…

• PDA is : "A stack" + "a finite state machine.“

• Pushdown automata can manage memory last-in-first-out with the

addition of stacks. An infinite amount of information can be stored in
pushdown automata.

• A pushdown automaton is made up of three parts:

1. an infinite-size stack,

2. a control unit, and

3. an input tape.
3
 Cont…

• The stack head examines the stack's top symbol. A stack performs two
tasks :

o Push: At the top, a new sign is inserted.

o Pop: The symbol at the top is read and eliminated.

• It is possible for a PDA to read input symbols or not, but every transition
requires it to read the top of the stack.

4
 Cont…

Input tape: There are many cells or

symbols on this tape. A single symbol
may only be entered at a time using the
input head, which is read-only.

Finite control: The finite control

contains a pointer pointing to the symbol
currently being read.

Stack: A stack is a structure in which

items are pushed and pulled from one
end only. It can have infinite size. Items
are temporarily stored on the stack in a
PDA.
5
 The Formal Definition of PDA

• In formal terms, a PDA is a 7-tuple (Q, ∑, S, δ, q0, I, F) −

o Q: is the number of finite states
o ∑: is the input alphabet
o S: is the stack symbol
o δ: is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
o q0: is an initial state, q0 (q0 ∈ Q)
o I: is the first stack top symbol (I ∈ S)
o F: is the set of accepted states (F ∈ Q)

6
 Acceptance by empty stack or final state

• A PDA can accept a string by either emptying the stack or reaching a final
state. These two modes of acceptance can be converted to each other.

1. Final State Acceptability:

• The final state acceptance of a string occurs after the PDA is ready after
reading the entire string.

• The starting state can be moved in a way that eventually leads to a final
state with any stack value. We don't care about the stack values as long as
7
we get to the final state.
 Cont…

2. Empty Stack Acceptability

• The PDA accepts a string after it has emptied its stack after reading the
entire string.

• The language accepted by the empty stack of a PDA (Q, ∑, S, δ, q0, I, F)

is L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}

8
PDA Transition Diagram

Input Stack top Push

symbol symbol symbol

q0 and q1 are States 9

• Example 1: Implement a PDA that accepts L = {anbn | n ≥ 1}

• This language accepts L = {ab, aabb, aaabbb, ............................. }, this

indicates the number of a's and b’s must be equal.

In this language whenever you get a, push it into the stack. Then whenever
you get b pop from the stack top. Take this example: aaabbb

S
T Initially, the stack is empty
A
c Z So that, Z is on the top of the stack

k Z is used to indicate we’re at the bottom of the stack

10
 Cont…

aaabbb

whenever you get symbol a, push it into the stack

S
T
A a Accepting the first symbol(a), then push into the stack
c
k Z

a will be on the top of the stack, in the form of (aZ)

11
 Cont…

aabbb

whenever you get symbol a, push it into the stack

S
T a Accepting the second symbol(a), then push into the
A stack
c a
k
Z

a will be on the top of the stack, in the form of (aaZ)

12
 Cont…

abbb
whenever you get symbol a, push it into the stack

a Accepting the third symbol(a), then push into the stack

S
T a
A
c a
k
Z
a will be on the top of the stack, in the form of (aaaZ)
13
 Cont…

bbb
whenever you get symbol b, pop from the stack (from the top of the stack )

Accepting the first symbol b, and Pop from the stack

S a
T
A a
c
k Z

a will be on the top of the stack, in the form of (aaZ)

14
 Cont…

bb

whenever you get symbol b, pop from the stack (from the top of the stack )

S Accepting the second symbol b, and Pop from the stack

T
a
A
c
Z
k

a will be on the top of the stack, in the form of (aZ)

15
 Cont…

whenever you get symbol b, pop from the stack (from the top of the stack )
S
T Accepting the last symbol b, and Pop from the stack
A
c Z
k

Z will be on the top of the stack, in the form of (Z)

Now our stack is empty, it will be accepted by an empty stack

16
 Cont…
The PDA diagram for L = {anbn | n ≥ 1}

Top of Push into

Input the stack the stack

17
 Cont…

1. Number of a’s and b’s are equal. So we can push a’s and then we can pop all a’s by b’s.
2. if the input a, and if the top of the stack is Z (Z indicated bottom of the stack), push a
into the stack (on the top of Z, which will be aZ). Stay at state q1. OR
3. if the input a, and if the top of the stack is a, push a into the stack (on the top of a,
which will be aa). Stay at state q1. then
4. if the input b, and if the top of the stack is a, then pop from the stack (push epsilon).
Repeat this step. Move from state q1 to q2. then
5. if the input epsilon, and if the top of the stack is Z, push epsilon (indicates the stack is
empty). Move from state q2 to q3. 18
• Example 2: Implement a PDA that accepts L = {anb2n | n ≥ 0}

• This language accepts L = {abb, aabbbb, ............................. }

• Some number of a’s followed by double number of b’s (2 * a’s). So that, to

make the stack empty we have to find ways. There are 2 ways to draw a PDA
that accepts this language

1. For every symbol a, push 2 a’s (in the stack we will have equal number a’s
and b’s, we can easily pop every a’s by b’s).

2. For every 2 b’s, pop one a (we push every a’s, the number of b’s will be
19
twice the number of a’s. we have to use two b’s for removing single a).
 Cont…
1. For every symbol a, push 2 a’s

1. if the input a, and if the top of the stack is Z, push aa into the stack (on the top of Z,
which will be aaZ). Stay at state q0. OR
2. if the input a, and if the top of the stack is a, push aa into the stack (on the top of a,
which will be aaa). Stay at state q0. then
3. if the input is b, and if the top of the stack is a, then pop from the stack (push epsilon).
Repeat this step. Move from state q0 to q1. then
4. if the input epsilon, and if the top of the stack is Z, push epsilon (indicates the stack is
20
empty). Move from state q1 to q2.
 Cont…
2. For every 2b’s, pop one a

if the input is b, and if the top of the stack is a, do nothing

(don’t push anything on the top of a)

21
 Exercise :

Implement a PDA that accepts L = {anb2n + 1 | n ≥ 1}

• {anb2n + 1} can be expressed as {anb2nb}. E.g. aabbbbb

• So that we can apply the two ways we used for{anb2n}, and then find a way to
remove tha last symbol b.
• all a’s will be poped by b’s in all methods, only single b will be left. The stack top
will be Z since all pushed symbols(a’s) are popped.
• The last input is b, the stack top is Z, then we don’t need to push or pop on the top
of the sack.
22
 Cont…

1. For every symbol a, push 2 a’s, and then remove the last single b

23
 Cont…

2. For every 2b’s, pop one a, and then remove the last single b

24
 Exercise 2:

1. Implement a PDA that accepts L = {anbncm | n, m ≥ 1}

2. Implement a PDA that accepts L = {anbmcn | n, m ≥ 1}

3. Implement a PDA that accepts L = {anbn + mcm | n, m ≥ 1}

4. Implement a PDA that accepts L = {anbmcn+ m | n, m ≥ 1}

25
 Cont…

1. Implement a PDA that accepts L = {anbncm | n, m ≥ 1}

• {anbncm}, indicates the number of a’s are equal with the number of b’s, but
number of c’s may may not be equal with number a’s or b’s.
• To recognize strings in this language, we can push every a’s into the stack, then
we can pop every a’s by b’s (since they are equal). Then
• c’s will be left, and the stack will be Z (since all a’s are popped)
• then accept c’s, the stack top is Z, and do nothing on the top of the stack

26
 Cont…

The PDA diagram for the above language:

Check the string aaabbbcc

27
 Cont…

2. Implement a PDA that accepts L = {anbmcn | n, m ≥ 1}

• {anbmcn}, indicates the number of a’s are equal with the number of c’s, but
number of b’s may may not be equal with number a’s or c’s.
• To recognize strings in this language, we can push every a’s into the stack, b’s are
at the middle, and the stack will be a (since all a’s are popped).
• Since the number of b’s may not equal with the number of b’s, we can’t pop all
a’s by b’s. so that, we accept b’s and we don’t do anything on the top of the stack
• then accept c’s, the stack top is a, and we can pop all a’s from the stack (since a’s
and c’s are equal). 28
 Cont…

The PDA diagram for the above language:

Check the string aaabbbbccc

29
 Cont…

3. Implement a PDA that accepts L = {anbn + m cm | n, m ≥ 1}

• {anbn + mcm} can be rewritten as {anbnbmcm}, and it is the same as {anbmbncm}

• We can push ever a’s into the stack
• We can pop a’s by accepting b’s until the stack top is Z
• If the input is, and if the stack top is Z, we need to push b’s into the stack
• Then pop all b’s by accepting c’s

30
 Cont…

The PDA diagram for the above language:

Check the string aaabbbbbcc

31
 Cont…

4. Implement a PDA that accepts L = {anbmcn+ m | n, m ≥ 1}

• {anbmcn+m} can be rewritten as {anbmcncm}, and it is the same as {anbmcmcn}

• The above language indicates the sum of a’s and b’s is equal to c’s. E.g. aabbbccccc
• a’s followed by b’s followed by c’s. so that.
• For every a’s and b’s, push into the stack
• For c’s pop from the stack (since by accepting all c’s we can pop all b’s and a’s)

32
 Cont…

The PDA diagram for the above language:

Check the string aabbbccccc

33
 Deterministic and non-deterministic pushdown automata

• A PDA is deterministic if there is only one move from a state on an input

symbol and stack symbol.

• A PDA is non-deterministic if there can be more than one move. Non-

deterministic PDAs have more expressive power than deterministic
PDAs.

34
 Cont…

Example 1: Implement a PDA that accepts L = {wcwR | w ∈ (a, b)+}

• wcwR indicates any string followed by c, then followed by the reverse of the
string, example abcba (ab follwed by c follwed by reverse of ab, which is ba),
aabcbaa(aab followed by c, followed by reverse of aab, which is baa).

• The alogrithm is: push alphabets into the stack until you get c, do nothing for
alphabet c, then pop from the stack starting from next to c to the end of the
alphabets.

• So that, we know that until which charater we need to push (c), and from which
character (next to c) we need to pop. So we use determininstic PDA
35
 Cont…

Deterministic PDA

1. if the input a, and if the top of the stack is Z, push a into the stack (on the top of Z,
which will be aZ). Stay at state q0. OR
2. if the input b, and if the top of the stack is Z, push a into the stack (on the top of Z,
which will be bZ). Stay at state q0. OR
3. if the input a, and if the top of the stack is a, push a into the stack (on the top of a,
which will be aa). Stay at state q0. OR
4. if the input b, and if the top of the stack is a, push a into the stack (on the top of a,
36
which will be ba). Stay at state q0…… OR
 Cont…

5. if the input b, and if the top of the stack is b, push b into the stack (on the top of b,
which will be bb). Stay at state q0. OR
6. if the input a, and if the top of the stack is a, push a into the stack (on the top of a,
which will be aa). Stay at state q0. OR
7. if the input b, and if the top of the stack is a, push a into the stack (on the top of a,
which will be ba). Stay at state q0. then
8. if the input c, and if the top of the stack is a, do nothing(leave the top as a, which will be
ba). Move from state q0 to q1. OR
9. if the input c, and if the top of the stack is b, do nothing(leave the top as b, which will
be ba). Move from state q0 to q1. then
10. if the input a, and if the top of the stack is a, pop from the stack. OR
11. if the input b, and if the top of the stack is b, pop from the stack. Then Move from state
q1 to q2.
12. If the input is epsilon, and the stack top is Z, push epsilon (empty stack)
37
Example 2: Implement a PDA that accepts L = {wwR | w ∈ (a, b)+}

• wwR indicates any string followed by the reverse of the string, example
abba (ab follwed by reverse of ab, which is ba), aabbaa(aab followed by
reverse of aab, which is baa).

• In this case we don’t know that until which character we need to push, and
from which character we need to pop. So we use non-deterministic PDA.

• The algorithm is: if the input symbol and the stack top are the different,
then push into the stack. if the input symbol and the stack top are the same
38
(take that symbol as center and pop from the stack).
 Cont…

Non-Deterministic PDA

39
 Let’s take an example aaaa Cont…

δ(q0, aaaa, Z)
(q0, aaa, aZ) Taking first symbol and push into the stack
Is the second a a center?
If a is not a center(push into the stack) If a is a center(pop from the stack)
(q0, aa, aaZ) (q0, aa, Z) ╳ No way when the input is
is the third a a center? a and the stack top is Z)

No Yes

(q0, a, aaaZ) (q0, a, aZ)

is the forth a a center? is the forth a a center?

No Yes No Yes

(q0, ε, aaaaZ) ╳ (q0, ε, aaZ) ╳

(q0, ε, aaZ) ╳ (q0, ε, Z) ✓

40
Stack must be empty
 Deterministic context-free language

• A deterministic context-free language (DCFL) is a proper subset of

context-free languages that can be accepted by a deterministic pushdown
automaton.

• DCFLs are always unambiguous, meaning that they admit an

unambiguous grammar.

Example: The language {a^n b^n | n >= 0} is a DCFL.

41
THE END!

42