Lecture 15 PDA

1. PUSH DOWN AUTOMATA (PDA)

Lecture #15
PUSH DOWN
AUTOMATA
(PDA)

2.

Pushdown automata are machines to accept contextfree languages.
For a context-free grammar G, there is an equivalent
pushdown automaton M to recognize the language
generated by the grammar G.

3.

Description of pushdown automaton
(PDA)
A PDA has
an input tape,
a finite control, and
a stack.
0
0
0
1
0
0
0
(input tape)
step1: read 0, push 0, and move to right
q1
q1
q1
(finite control)
step2: read 0, push 0, and move to right
0
0
(stack)

4.

There are 2 types of moves (Non-determinstic):
1. According to an input symbol, current state, and
top symbol of the stack, a decision is made, then
the input head is moved ahead one symbol.
2. Next move is decided by the current state and the
top symbol of the stack only. The input symbol
is not used. Hence the input head is not moved at
all after the decision is made. This type of move
is called ε-move that allows the PDA to
manipulate the stack without reading input
symbol.

5.

Languages accepted by PDA's
There are two ways to accept inputs:
1. The PDA accepts an input if after reading the
input and the machine empty its stack.
The set of inputs accepted by the PDA is the
language accepted by empty stack.
2. Some states of the PDA are final states. The
PDA accepts an input if the machine enters a
final state.
The set of inputs accepted by the PDA is the
language accepted by final state.

6.

Definition of PDA's

7.

Moves:
0
0
1
0
δ
0
0
1
0
B
G
G
R
R

8.

-Moves: