Xem mẫu
- Lecture # 28
Theory Of Automata
By
Dr. MM Alam
1
- Lecture 27 recap
•
Chomsky Normal Form conversion in
JFLAP
•
Push Down Automata Definition
•
PDA Symbols
2
- Adding A Pushdown Stack
•
A PUSHDOWN STACK is a place where input
letters can be stored until we want to refer to them
again.
•
It holds the letters it has been fed in a long line.
The operation PUSH adds a new letter to the line.
•
The new letter is placed on top of the STACK, and
all the other letters are pushed back (or down)
accordingly.
•
Before the machine begins to process an input string
the STACK is presumed to be empty, which means
3
that every storage location in it initially contains a
- Adding A Pushdown Stack
•
If the STACK is then fed the letters a, b, c, d by
this sequence of instructions:
PUSH a
PUSH b
PUSH c
PUSH d
•
Then top letter in the STACK is d, the second is c,
the third is b, and the fourth is a.
•
If we now execute the instruction:
•
PUSH b the letter b will be added to the STACK on
the top. The d will be pushed down to 4position 2,
- Adding A Pushdown Stack
•
One pictorial representation of a STACK with these
letters in it is shown below.
•
Beneath the bottom a we presume that the rest of
the STACK, which, like the INPUT TAPE, has
infinitely many storage locations, holds only blanks.
b
d
c
b
a
Δ
5
- Adding A Pushdown Stack
•
How the following PDA is working:
a
b
6
- Adding A Pushdown Stack
•
Its operation on the
•
input string aaabbb.
•
We begin by assuming
•
that this string has
•
been put on the TAPE.
STACK
Δ
TAPE a a a b b b Δ
7
- Adding A Pushdown Stack
•
Its operation on the
•
input string aaabbb.
•
We begin by assuming
•
that this string has been
•
put on the TAPE.
STACK
a
Δ
TAPE a a a b b b Δ
8
- Adding A Pushdown Stack
•
We now read another a
•
and proceed as before along
•
the a edge to push it into
•
the STACK.
•
Again we are returned
•
to the READ box.
STACK
•
Again we read an a (our third),
•
and again this a is pushed onto the STACK.a
a
TAPE a a a b b b Δ a
Δ
9
- Adding A Pushdown Stack
•
After the third PUSH a,
•
we are routed back to
•
the same READ state again.
•
This time, we read the letter b.
•
This means that we take the
•
b edge out of this state down
STACK
•
to the lower left POP.
a
a
TAPE a a a b b b Δ Δ
10
- Adding A Pushdown Stack
•
The b road from the second
•
READ state now takes us
•
back to the edge feeding
•
into the POP state.
•
So we pop the STACK
•
again and get another a.
•
The STACK is now
•
down to only one a. a
•
The a line from POP Δ
•
takes TAPE a to
us again a this
a bsameb READ.
b Δ
•
There is only one letter left on the input TAPE, a b.
STACK
11
- Adding A Pushdown Stack
•
We read it and
•
leave the TAPE empty,
•
that is, all blanks.
•
However, the machine does
•
not yet know that the TAPE
•
is empty.
•
It will discover this only when
•
it next tries to read the TAPE Δ
•
and TAPE
finds Δ. a a a b b b Δ
12
- Adding A Pushdown Stack
•
Let
13
- Adding A Pushdown Stack
14
- Example
Example
•
The PALINDROMEX, language of all words of the
form s X reverse(s) where s is any string in (a +
b)*.
•
The words in this language are
{ X aXa bXb aaXaa abXba baXab bbXbb aaaXaaa aabXbaa
...}
•
They all contain exactly one X, and this X marks
the middle ofthe word.
•
We can build a deterministic PDA that accepts the
language PALINDROMEX.
•
It has the same basic structure as the PDA we had
for the language {anbn}. 15
- Adding A Pushdown Stack
Example
•
In the first part of the machine the STACK is loaded
with the letters from the input string just as the
initial a's from anbn were pushed onto the STACK.
•
The letters go into the STACK first letter on the
bottom, second letter on top of it, and so on till the
last letter pushed in ends up on top.
•
When we read the X we know we have reached
the middle of the input.
16
- Adding A Pushdown Stack
Example
•
We can then begin to compare the front half of the
word (which is reversed in the STACK) with the
back half (still on the TAPE) to see that they match.
•
We begin by storing the front half of the input string
in the STACK with this part of the machine.
17
- Adding A Pushdown Stack
Example
•
If we READ an a, we PUSH an a. If we READ a
b, we PUSH a b, and on and on until we encounter
the X on the TAPE.
•
After we take the first half of the word and stick it
into the STACK, we have reversed the order of the
letters and it looks exactly like the second half of
the word.
•
For example, if we begin with the input string
abbXbba
18
- Adding A Pushdown Stack
Example
•
At the moment we are just about to read the X we
have:
b
b
a b b X b b a Δ
a
Δ
19
- Adding A Pushdown Stack
Example
•
When we read the X we do not put it into the
STACK. It is used up the process of transferring us
to phase two.
•
In order to reach ACCEP these two should be the
same letter for letter, down to the blanks.:
20
nguon tai.lieu . vn
