Pushdown automata

1. Pushdown
Automata
PDAs

2. Pushdown Automaton --
PDAInput String
Stack
States

3. Initial Stack Symbol
Stack$ Stackz
bottom
special symbol

4. The Statesq
1 q
2 a,bc
Input
symbol
Pop
symbol
Push
symbol

5. q
1 q
2 a,bc a   b top
input
stacka  
Replacee h $ e h $ c

6. q
1 q
2 a, c a   a   Pushb e h $ e h $ b c
top
input
stack

7. q
1 q
2 a,b a   a   Popb e h $ e h $
top
input
stack

8. q
1 q
2 a, a   a   No Changeb e h $ e h $ b
top
input
stack

9. Non-Determinismq
1 q
2 a,bc q
3 a,bc q
1 q
2 ,bc transition
These are allowed transitions in
a Non-deterministic PDA (NPDA)

10. NPDA: Non-Deterministic
PDA
Example:, a,a b,a q
0 q
1 q
2 q
3 b,a ,$$

11. a,a b,a 0
q q
1 q
2 q
3 Execution Example:
Inputa a a b b b
current
stateb,a
Time 0, ,$$
Stack$

12. a,a b,a q
0 q
1 q
2 q
3 Inputa a a b b b b,a
Time 1, ,$$
Stack$

13. a,a b,a q
0 q
1 q
2 q
3 Input
Stacka a a b b b $ a b,a
Time 2, ,$$

14. a,a b,a q
0 q
1 q
2 q
3 Input
Stacka a a b b b $ a a b,a
Time 3, ,$$

15. a,a b,a q
0 q
1 q
2 q
3 Input
Stacka a a b b b $ a a a b,a
Time 4, ,$$

16. a,a b,a q
0 q
1 q
2 q
3 Inputa a a b b b
Stack$ a a a b,a
Time 5, ,$$

17. a,a b,a q
0 q
1 q
2 q
3 Inputa a a b b b $ a
Stackb,a
Time 6, ,$$ a

18. a,a b,a q
0 q
1 q
2 q
3 Inputa a a b b b $
Stackb,a
Time 7, ,$$ a

19. a,a b,a q
0 q
1 q
2 q
3 Inputa a a b b b b,a
Time 8
accept, ,$$ $
Stack

20. A string is accepted if there is
a computation such that:
•All the input is consumed
•The last state is a final state
At the end of the computation,
we do not care about the stack contents
The Language of PDA

21. Formal Definition
Non-Deterministic Pushdown Automaton
NPDA),,,δ,Γ,Σ,(
0
FzqQM
States
Input
alphabet
Stack
alphabet
Transition
function
Final
states
Stack
start
symbol
Initial
state

22. Instantaneous Description),,( suq
Current
state
Remaining
input
Current
stack
contents

23. Acceptance by Final State
L(M)= set of all strings w such that starting
from initial ID machine consumes w from
input and enters an accepting state.
The contents of the stack at that time is
irrelevant.
{w | (q0, w, Z)
*
(q, ,)
For some final state q of F and any stack
staring .

24. Acceptance by empty
stack
N(M) = (w | (q0,w,Z)
*
(q,,)
That is N(M) is the set of all strings w such
that M can consume w and at the same
time empties its stack.Here we do not
care whether q is a final state or not.

25. The input string
is accepted by the NPDA:aaabbb a,a b,a q
0 q
1 q
2 q
3 b,a , ,$$

26. }0:{ nbaL
nn is the language accepted by the NPDA:a,a b,a q
0 q
1 q
2 q
3 b,a
In general,, ,$$

27. Another NPDA example,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
,
NPDA M }{)(
R
wwML

28. Execution Example:
Input
Time 0
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a b b

29. Inputa a b
Time 1
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b

30. Input
Time 2
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a a b b b

31. Input
Time 3
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a a b b b
Guess the middle
of string

32. Input
Time 4
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a a b b b

33. Input
Time 5
Stack$ ,$$ 1q q
2 bb
aa
,
, , q
0 bb
aa
,
, a a b b a

34. Input
Time 6
Stack$ ,$$ q
1 bb
aa
,
, , q
0 bb
aa
,
, a a b b
acceptq
2

35. Rejection Example:
Input
Time 0
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b b b

36. Input
Time 1
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a b b b

37. Input
Time 2
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b a b b b

38. Input
Time 3
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b
Guess the middle
of stringa b b b

39. Input
Time 4
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b a b b b

40. Input
Time 5
Stack$ ,$$ 1q q
2 bb
aa
,
, , q
0 bb
aa
,
, a a b b b
There is no possible transition.
Input is not
consumed

41. Another computation on same string:
Input
Time 0
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b b b

42. Input
Time 1
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a a b b b

43. Input
Time 2
Stack$ ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, a b a b b b

44. Input
Time 3
Stack$ a b a b b b ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, b

45. Input
Time 4
Stacka b b b ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, $ a b b b

46. Input
Time 5
Stacka b b b $ a b b b ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
,
No final state
is reached

47. ,$$ q
1 q
2 bb
aa
,
, , q
0 bb
aa
,
, There is no computation
that accepts stringabbb )(MLabbb

48. Pushing Stringsq
1 q
2 a,bw
Input
symbol
Pop
symbol
Push
string

49. q
1 q
2 a,bcdf a   b top
input
stacka  
Pushe h h e c d f
pushed
string
Example:$ $

50. Another NPDA example$$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0
NPDA M }:{)(
ba
nnwML

51. Time 0
Inputa a b b b
current
statea $
Stack$$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0
Execution Example:

52. Time 1
Inputa a b b b a $
Stack0 $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0

53. Time 3
Inputa b b b a $
Stacka $ $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0 0

54. Time 4
Inputa b b b a $
Stacka 1 $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0

55. Time 5
Inputa b b b a $
Stacka 1 1 $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0

56. Time 6
Inputa b b b a $
Stacka 1 $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0 1

57. Time 7
Inputa b b b a $
Stacka 1 $$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0

58. Time 8
Inputa b b b a a $
Stack$$, q
1 q
2 a,$0$ a,000 a,1 b,$1$ b,111 b,0
accept

59. Formalities for
NPDAs

60. q
1 q
2 a,bw )},{(),,(
21 wqbaq Transition function:

61. q
1 q
2 wba, q
3 wba, )},(),,{(),,(
321
wqwqbaq Transition function:

62. Formal Definition
Non-Deterministic Pushdown Automaton
NPDA),,,δ,Γ,Σ,(
0
FzqQM
States
Input
alphabet
Stack
alphabet
Transition
function
Final
states
Stack
start
symbol
Initial
state

63. Instantaneous Description),,( suq
Current
state
Remaining
input
Current
stack
contents

64. a,a b,a q
0 q
1 q
2 q
3 Input
Stacka a a b b b $ a a b,a
Time 4:, ,$$
Example: Instantaneous Description$),,(
1 aaabbbq a

65. a,a b,a q
0 q
1 q
2 q
3 Input
Stacka a a b b b $ a a b,a
Time 5:, ,$$
Example: Instantaneous Description$),,(
2aabbq a

66. We write:$),,($),,(
21 aabbqaaabbbq 
Time 4 Time 5

67. a,a b,a q
0 q
1 q
2 q
3 b,a , ,$$ ,$),(,$),($),,($),,(
$),,($),,($),,(
,$),(,$),(
3222
111
10
qqabqaabbq
aaabbbqaaabbbqaaabbbq
aaabbbqaaabbbq


 A computation:

68. ,$),(,$),($),,($),,(
$),,($),,($),,(
,$),(,$),(
3222
111
10
qqabqaabbq
aaabbbqaaabbbqaaabbbq
aaabbbqaaabbbq


 For convenience we write:,$),(,$),(
30 qaaabbbq 

69. Formal Definition
Language of NPDA :M )}',,(),,(:{)(
0 sqswqwML
f
Initial state Final state

70. Example:,$),(,$),(
30
qaaabbbq  a,a b,a q
0 q
1 q
2 q
3 b,a , ,$$
NPDA :M )(MLaaabbb

71. ,$),(,$),(
30
qbaq
nn
 a,a b,a q
0 q
1 q
2 q
3 b,a , ,$$ NPDA :M )(MLba
nn

72. a,a b,a q
0 q
1 q
2 q
3 b,a , ,$$ NPDA :M }0:{)( nbaML
nn
Therefore:

73. NPDAs Accept
Context-Free
Languages

74. Context-Free
Languages
(Grammars)
Languages
Accepted by
NPDAs
Theorem:

75. Context-Free
Languages
(Grammars)
Languages
Accepted by
NPDAs
Proof -Step 1:
Convert any context-free grammar
to a NPDA with: G M )()( MLGL

76. Context-Free
Languages
(Grammars)
Languages
Accepted by
NPDAs
Proof -Step 2:
Convert any NPDA to a context-free
grammar with: G M )()( MLGL

77. Converting
Context-Free
Grammars
to
NPDAs

78. An example grammar:T
TaT
bS
aSTbS
What is the equivalent NPDA?

79. q
0 q
1 2q S, ,$$ Grammar:
NPDA:T
TaT
bS
aSTbS
,
,
,
, T
TaT
bS
aSTbS bb
aa
,
,

80. The NPDA simulates
leftmost derivations of the grammar
L(Grammar) = L(NPDA)

81. Grammar:T
TaT
bS
aSTbS
A leftmost derivation:abababTababTbaSTbS

82. NPDA execution:0
q q
1 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
,
Input
Stack$ a a b
Time 0b
current
state

83. q
0 q
1 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 1b S

84. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 2b a b S T q
1

85. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 3b a b S T q
1

86. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 4b b T b q
1

87. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 5b b T b q
1

88. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 6b b T a q
1

89. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 7b b T a q
1

90. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 8b b a q
1

91. q
0 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 9b b q
1

92. q
0 q
1 2q S, ,$$ T
TaT
bS
aSTbS
,
,
,
, bb
aa
,
, Input
Stack$ a a b
Time 10b
accept

93. In general:
Given any grammar G
We can construct a NPDA M
With)()( MLGL

94. Constructing NPDA from grammar :q
0 q
1 2q S, ,$$ wA, aa, M
For any productionwA For any terminala G

95. Grammar generates string G w
if and only if
NPDA acceptsM w )()( MLGL

96. Therefore:
For any context-free language
there is an NPDA
that accepts the same language

97. Converting
NPDAs
to
Context-Free
Grammars

98. For any NPDAM
we will construct
a context-free grammar withG )()( GLML

99. Intuition:G The grammar simulates the machine
A derivation in Grammar :  abcABCabcS
Current configuration in NPDA M

100. in NPDAM  abcABCabcS
Input processed Stack contents
terminalsvariablesG
A derivation in Grammar :

101. Some Necessary
Modifications First, we modify the NPDA:
•It has a single final state
•It empties the stack
when it accepts the input
Original NPDA Empty Stackfq fq

102. Second, we modify the NPDA transitions:
all transitions will have formiq j
q Ba,
oriq j
q CDBa, symbolsstack :,,DCB

103. $, 0q fq a,$0$ a,000 a,1 b,$1$ b,111 b,0 }:{)(
ba
nnwML Example of a NPDA in correct form:symbolstack initial :$

104. The Grammar
Construction)(
ji
Bqq
In grammar :G
Terminals:
Input symbols of NPDA
states
Stack symbol
Variables:

105. iq j
q Ba, For each transition
We add productionaBqq
ji
)(

106. For each transition
We add production))(()(
klljki
DqqCqqaBqq iq j
q CDBa,
For all states lkqq,

107. Start Variable:)$(
fo
qq
Stack bottom symbol
Start state final state

108. Example:$, 0q fq a,$0$ a,000 a,1 b,$1$ b,111 b,0 aqq)1(
00
Grammar production:

109. Example:$, 0q fq a,$0$ a,000 a,1 b,$1$ b,111 b,0 )$)(1(|)$)(1()$(
)$)(1(|)$)(1()$(
00000
00000000
fffff
ff
qqqqbqqqqbqq
qqqqbqqqqbqq
Grammar productions:

110. Example:$, 0q fq a,$0$ a,000 a,1 b,$1$ b,111 b,0
Grammar production:)$(
0f
qq

111. )$)(1(|)$)(1()$(
)$)(1(|)$)(1()$(
00000
00000000
fffff
ff
qqqqbqqqqbqq
qqqqbqqqqbqq )1)(1(|)1)(1()1(
)1)(1(|)1)(1()1(
00000
00000000
fffff
ff
qqqqbqqqqbqq
qqqqbqqqqbqq )$)(0(|)$)(0()$(
)$)(0(|)$)(0()$(
00000
00000000
fffff
ff
qqqqaqqqqaqq
qqqqaqqqqaqq Resulting Grammar:ablestart vari:)$(
0f
qq

112. )0)(0(|)0)(0()0(
)0)(0(|)0)(0()0(
00000
00000000
fffff
ff
qqqqaqqqqaqq
qqqqaqqqqaqq bqq
aqq
)0(
)1(
00
00 )$(
0f
qq

113. Derivation of stringabba )$(
0f
qq )$)(0(
000 f
qqqqa )$(
0f
qqab )$)(1(
000 f
qqqqabb )$(
0f
qqabba abba

114. In general, in Grammar:wqq
f)$(
0
if and only ifw
is accepted by the NPDA

115. Explanation:
By construction of Grammar:wAqq
ji)(
if and only if
in the NPDA going from to
the stack doesn’t change below
and is removed from stack i
q j
q A A