Two-Stack PDA

CS6800
Advance Theory of Computation
Spring 2016

Nasser Alsaedi

1
 Outlines

 Turing Machine as a Model of Computation

 Two-Stack PDA is Equivalent to TM

 Linear Bound Automata with One Stack

 Linear Bound Automata with Two Stacks

 TM Simulate Two-Stack PDA

2
 Turing Machine
Turing Machine is a powerful computing model that can simulate
any computer program.
Input string

a b c d e
Infinite Tape

a b c d e
Head moves left or right

Finite State
Control Unit
3
 The Turing Machine
Hopcroft and Ullman [1] defined a one-tape Turing machine
as sextuples (Q, Γ, ∑, , q0, F) where:

•Q is a finite set of states.

•Γ is a finite set of the tape alphabet/symbols contain a special symbol B
that represent a blank.
•Σ is a subset of Γ – {B} called input alphabet.
• = Q x Γ  Q x Γ x {L,R} is a partial function called the transition
function, where L is left shift, R is right shift.
•q0 is the initial state.
•F is the set of final or accepting states.

4
 Turing Machine as Model of Computation

 Turing Machine is a model of computation.

 Equivalent versions of Turing machine have the same power

as the standard Turing machine.
− Two way Turing Machine
− Multitrack Turing Machine
− Multitape Turing Machine
− Non-deterministic Turing Machine

 Any machine that simulates any computer program can

be considered as model of computation.

 Undecidable Problem can be apply to any computational

model (not restricted to the Turing machine).
5
 Two-Stack PDA
 A Turing machine can accept languages not accepted
by any PDA with one stack.

 The strength of pushdown automata can be increased by

adding additional (extra) stacks.

 Actually, a PDA with two stacks has the same

computation power as a Turing Machine.

6
 Two-Stack PDA
Input Tape

Tape Head
Head moves from left to write

Finite state
control unit

Stack 1 Stack 2

7
 Two-Stack PDA
k-Stack PDA is also called k-stack machine.

Adding more than two stacks to multistack machine does

not increase the power of computation.

Theorem (8.13) (Hopcroft and Ullman [1]):

If a language L is accepted by a Turing machine, then L
is accepted by a two-stack machine.

8
 Two-Stack PDA
 Two-Stack PDA is a computational model based on the
generalization of Pushdown Automata (PDA).

 Non-deterministic Two-Stack PDA is equivalent to a

deterministic Two-Stack PDA.

 The move of the Two-Stack PDA is based on

− The state of the finite control.
− The input symbol read.
− The top stack symbol on each of its stacks.

9
 Turing Machine Two-Stack PDA Machine

A move of Turing machine includes: A move of two-stack PDA includes:

A. Change state A. Change state

B. Write a tape symbol in the B. The input symbol read

cell scanned
C. Replace the symbol of
C. Move the head left or right. each stack with a string of
zero or more stack symbol

How does the Two-Stack PDA simulate the TM tape ?

10
Two-Stack PDA Simulate TM
How does the Two-Stack PDA simulate the TM tape ?

The idea is that the first stack can hold what is to the left of the head,
while the second stack holds what is to the right of the head.

When we want to get a symbol which is in the first stack , we will pop all
the content in the first stack above that symbol and push these content
in the second stack.

In this way we can access any symbol stored in the stack without losing
any content.

This allows to simulate the tape of TM M , where the TM head is

corresponding to the heads of the two stacks of the Two-Stack PDA .

11
TM M
Two-Stack PDA S

M Tape
b
a b b a c d e a

c
a d
b e
b a
a b
# #

Stack1 Stack2

12
M replaces X by Y and moves right

X M Tape

a b b Y c d e a b

Move right

Pop X
c
Push Y d
b e
b a
a b
# #

Stack1 Stack2

S pop X from stack2 and push Y to stack1

13
M replaces X by Y and moves left
X M Tape

a a b z Y c d e b

Move left

z push z
Pop X Y push Y
Pop z c
b d
a e
a b
# #

Stack1 Stack2

S pop X and Z from stack1 and push ZY to stack2

14
 Pushdown Automata
Sudkamp [2] defined A pushdown automata (PDA) as a
sextuple (Q, , , , q0, F), where
 Q is a finite set of states
  is a finite set of input symbols, called input alphabet
  is a finite set of stack symbols, called stack alphabet
 q0  Q, is the start state
 F  Q, is the set of final states
 : Q  (  {  })  (  {  })  to the set of all subsets of
Q  (  {  }), a (partial) transition function

15
 Pushdown Automata
Input Tape

Tape Head
Head moves from left to right

state control
Stack

PDA = FSA+ memory (stack)

16
 PDA
The transition  is of the form:
[qj, B]  (qi, a, A),
where
 qi is the current state
 a is the current input symbol
 A is the current top of the stack symbol
 qj is the new state
 B is the new top of the stack symbol

qi a A/B qj qi a A/ qj

qi a  / qj

17
 Accepting Criteria
There are two criteria for string acceptance by PDA.
 First Criteria (final state and empty stack)
An input string x is accepted by the PDA if the PDA stops at a
final state and the stack is empty. Otherwise, the input string is
rejected.
 Second Criteria (final state only)
An input string x is accepted by the PDA if the PDA stops at a final
state no matter what symbols in the stacks.

Let L be a language accepted by a PDA M (Q, , , , q0, F)

with acceptance defined by final state. Then there is a PDA that
accepts L by final state and empty stack.
18
 Context-Free Grammar (CFG)

Productions
uv

String of variables
One variable
and terminals

A language L is context-free if there exists a CFG G such that L = L(G).

Theorem:
Let L be a context-free language, then there is a PDA that accepts L.

19
 The language {anbn } is context-free:
If (n > 0) , the context-free grammar as follow:

S  aAB | aB
A  aAB | aB
Bb
If (n  0) , the context-free grammar as follow:

S  aSb
S 
20
 PDA
Example (Sudkamp [2]) PDA accepts the language L = { anbn |n  0}. The
stack is used to record the number of a’s

a /A b A/
Computational Trace
b A/ [q0, aaabbb , ]
> q0 q1
|- [q0, aabbb, A]
M = {q0 , q1 } |- [q0, abbb, AA]
|- [q0, bbb, AAA]
 = {a, b } |- [q1, bb, AA]
 = {A} |- [q1, b, A]
F = {q0 , q1 } |- [q1, , ]
(q0, a, ) = { [q0 , A] }
(q0, b, A) = { [q1 , ] }
(q1, b, A) = { [q1 , ] }
21
 Pushdown Automata is non-deterministic

PDA accepts the language L = { anbn |n  0}.

a /A b A/

b A/
> q0 q1

OR

a /A b A/

  /
> q0 q1

22
 PDA
Example 8.1.1 (Sudkamp [2]) A PDA accept the language L= {wcwR |w ={a,b}*}.
The stack is used to record the string w. stack symbols A and B represent the
input a and b respectively.

Q = {q0 , q1 } b /B b B/

a /A a A/
 = {a, b ,c }
 = {A ,B}
c  /
F = { q1 } > q0 q1

(q0, a, ) = { [q0 , A] }
(q0, b, ) = { [q0 , B] }
(q0, c, ) = { [q1 , ] }
(q1, a, A) = { [q1 , ] }
(q1, b, b) = { [q1 , ] }
23
 Computational Power of PDA

 PDA accepts only context sensitive languages.

 Some languages can not be accepted by PDA.

Example of languages not accepted by PDA

Language Machine Grammar
L = { aibici | i > 0 } LBA Context sensitive
L = { aibicidi | i  0 } TM Unrestricted
L = { aibicidiei | i  0 } TM Unrestricted

24
 Context-Sensitive Grammar (CSG)
Productions
uv

String of variables String of variables

and terminals and terminals

and |u|  |v|

A language L is context-sensitive if there exists a CSG G such that L = L(G).

Theorem:
Let L be a context-sensitive language, then there is a linear-bounded
automata M with L(M)= L.
25
The language b c | n  0} is context-sensitive:
n n n
{a

It can be generated by a context-sensitive grammar

S  abc | aAbc
Ab  bA
Ac  Bbcc
bB  Bb
aB  aa | aaA
26
 Linear Bounded Automata
A linear bounded automata (LBA) is a nondeterministic
Turing machine that restricts the tape to the length of
the input with two boundary cells contain endmarkers.

LBA is the same as Turing Machines

with one difference:
The input string tape space
is the only tape space allowed to use

27
 Linear Bounded Automaton (LBA)

Input string
[ a b c d e ]

Left-end Right-end
marker Finite State marker
Control Unit

All computation is done between end markers

28
 Unrestricted Grammars
Productions

uv

String of variables String of variables

and terminals and terminals

Theorem:
A language L is recursively enumerable if and only if L
is generated by an unrestricted grammar.
29
Example of unrestricted grammar

S  aAc
aA  cB
Bc  d

30
 The Chomsky Hierarchy

Non-recursively enumerable

Recursively-enumerable
Recursive

Context-sensitive

Context-free

Regular
31
 Two-Stack PDA
Definition 8.6.1 Sudkamp [2] A two-stack PDA is a
sextuple (Q, , , , q0, F), where Q, , , q0, and F are the
same as in a one-stack PDA. The transition function as follow:
: Q  (  {  })  (  {  })  (  {  })  to the set of all
subsets of Q  (  {  })  (  {  })

The two stacks of the PDA are independent.

one stack: two stack:

qi a A/ qj qi a A/ /B/C qj

Two-Stack PDA accepts any language that accepted by a

Turing Machine.
32
 Two-Stack PDAs
Two-Stack PDA accepts the language L= { aibici | i  0 }
a /A / b A/ /B c / B/

> q0 q1 q2
b A/ /B c / B/

OR
a /A / c / B/
 / /
> q0 q2

b A/ /B c / B/

q1
b A/ /B 33
Example 8.6.1 (Sudkamp [2]) A Two-Stack PDA M accepts L = { aibici | i  0 }

a /A / c / B/

 / /
> q0 q2

b A/ /B c / B/

q1
b A/ /B

Computational Trace
Q = {q0 , q1 , q2} [q0, aabbcc, , ] |- [q0, abbcc, A, ]
 = {a, b ,c } |- [q0, bbcc, AA, ]
 = {A ,B} |- [q1, bcc, A, B]
F = { q2 } |- [q1, cc, , BB]
|- [q2, c, , B]
|- [q2, , , ]
34
 Two-Stack PDAs
Example 8.6.2 (Sudkamp [2]) A Two-Stack PDA M accepts the
language L = { aibicidi | i  0 }

a /A / d C/ /

 / /
> q0 q3

b A/ /B d C/ /

q1 q2
b A/ /B c /C B/ c /C B/

The computations of M process the strings of L in the following manner:

i) Processing a pushes A onto stack 1.
ii) Processing b pops A and pushes B onto stack 2.
iii) Processing c pops B and pushes C onto stack 1.
iv) Processing d pops C.
35
 Two-Stack PDA
Theorem 8.13 (Hopcroft and Ullman [1])
If a language L is accepted by a Turing machine, L is
accepted by a Two-Stack machine.

36
 Theorem Proof
The idea is that the first stack can hold what is
to the left of the head, while the second stack
holds what is to the right of the head,
neglecting all the infinite blank symbols beyond
the leftmost and rightmost of the head.

The proof is taken from (Hopcroft and Ullman [1])

37
 Proof Cont’d
Let’s L be L(M) for some one tape TM M,
two-stack machine S, simulating a one-tape
TM M as the following:

1. S begins with a bottom-of-stack marker

on each stack, this marker considered the
start symbol for the stacks, and must not
appear elsewhere on the stacks. The marker
indicates that the stack is empty.
38
 Proof Cont’d
2. Suppose that w$ is on the input of S. S
copies the input w onto its first stack, and
stops to copy when reading the endmarker
on the input.
3. S pops each symbol in turn from its first
stack and pushes it onto its second stack.
The first stack of S is empty. The second
stack holds w, with the left end of w is at
the top.

39
 Proof Cont’d
4. S simulated the first state of M. The empty
first stack indicates the fact that M has a
blank to the left of cell scanned by the tape.
S has a second stack holding w indicates
the tape head point to the left most symbol
in the string w ( see the following diagram).

40
 M Tape

a b c d e

M Head

e a
d b
c c
b d
a e
Marker # Marker #

Stack1 Stack2

S push the input to stack1

S pop the input from stack1 and push it to stack2
41
 Proof Cont’d
5. S simulates a move of M as follows:

a) S knows the state of M, say q, because S

simulates the state of M in its own finite control.

b) S knows the symbol X scanned by the head of

M; it’s at the top of the second stack. If the
second stack contains only the bottom of stack
marker , this means that M’s head has just
scanned a blank.

c) So, S knows the next move of M.

42
 Proof Cont’d
d) The next state of M is recorded in a component
of S’s finite control, instead of the previous
state.

e) If M replaces X by Y and moves right, then S

pushes Y onto its first stack, representing the fact
that Y is now at the left of M’s head (see the
following diagram).

43
M replaces X by Y and moves right

X M Tape

a b b Y c d e a b

Move right

Pop X
c
Push Y Y d
b e
b a
a b
# #

Stack1 Stack2

S pop X from stack2 and push Y to stack1

44
 Proof Cont’d
f) If M replace X by Y and moves left, S pops the
top of the first stack , say Z, then replaces X by
ZY on the second stack. This represents what used
to be one position left of the head is now at the head
(see the following diagram).

45
M replaces X by Y and moves left
X M Tape

a a b z Y c d e b

Move left

z push z
Pop X Y push Y
Pop z c
b d
a e
a b
# #

Stack1 Stack2

S pop X and Z from stack1 and push ZY to stack2

46
 Proof Cont’d
6. S accepts if the new state of M is accepting.
Otherwise, S simulates another move of
M in the same manner.

47
 TM can Simulate Two-Stack PDA
Pushdown automata is non-deterministic. Therefore, we choose a non-
deterministic Turing machine M to simulate the Two-Stack PDA.

 We split the tape of the turing machine into two half.

 We place a marker symbol in the tape to indicate the border between
the two half.
 The part of the tape left from the marker simulate one stack.
 The part of the tape right from the marker simulate the second stack.
 The bottom of the stack is the marker.

- We can simulate the two stacks using two-tape Truing machine

such that every tape simulates one stack.

48
 M Tape

a b b a # c d a b

Marker indicates the two border of the tape

a b
b a
b d
a c
# #

Stack 1 Stack 2

49
Question : Does the Two-Stack PDA simulate the computer?

Answer: yes

Since TM simulates a computer (proven in the course text book)

AND Two-Stack PDA simulates a TM (proven in Hopcroft and Ullman [1])

Thus , Two-Stack PDA can simulate the computer.

50
References

1- Hopcroft J , Motwani R, Ullman J , “Introduction to Automata Theory,

Languages and Computation”, Addison Wesley, 2nd edition , 2001.

2- T. A. Sudkamp , “Language and Machine: An Introduction to the

Theory of Computer Science” Addison-Wesley , 2nd edition , 1997.

51