Xem mẫu
- Lecture # 29
Theory Of Automata
By
Dr. MM Alam
1
- Lecture 28 at a Glance…
•
Push Down Automata Definition
•
PDA Symbols
•
Deterministic PDA Examples
•
Non-Deterministic PDA Examples
2
- Pushdown Automata
•
Example
•
Consider the language generated by the
CFG:
S→ S+SIS *S|4
•
The terminals are +, *, and 4 and the only
nonterminal is S.
3
- Pushdown Automata
•
The following PDA accepts this language:
4
- Pushdown Automata
•
Example
•
Trace the acceptance of 4 + 4 * 4
STATE STACK TAPE
START Δ 4 +4 * 4
PUSH1 S S 4 +4 * 4
POP Δ 4 +4 * 4
PUSH2 S S 4 +4 * 4
PUSH3 + +S 4 +4 * 4
PUSH4 S S+S 4 +4 * 4
5
- Pushdown Automata
•
Example
•
Trace the acceptance of 4 + 4 * 4 (continued)
STATE STACK TAPE
POP +S 4 +4 * 4
READ1 +S 4*4
POP S 4*4
READ2 S 4*4
POP Δ 4*4
PUSH5 S S 4*4
PUSH6 * *S 4*4
PUSH7 S S*S 4*4
POP *S 4*4
READ1 *S *4
6
- Pushdown Automata
•
Example
•
Trace the acceptance of 4 + 4 * 4 (continued)
POP S *4
READ3 S 4
POP Δ 4
READ1 Δ Δ
POP Δ Δ
READ4 Δ Δ
ACCEPT Δ Δ
7
- Theorem
Statement:
Given a language L generated by a
particular CFG, there is a PDA that
accepts exactly L.
8
- PDA
Conversion to
CFG
STACK alphabet :
Γ = {S, A, B, C}
TAPE alphabet:
S = {a, b}
Let us consider the following CFG in
CNF
S → SB
S → AB
A → CC The nondeterministic
B→b PDA.
C → a. 9
- PDA Conversion to CFG
•
The word aab can be generated by most
derivation in this grammar as follows:
Working-String Generation Production Used
S => AB S → AB Step I
=>CCB A → CC Step 2
=>aCB C→a Step 3
=>aaB C→a Step 4
=> aab B→b Step 5
10
- PDA Conversion to CFG
•
We start with
STACK TAPE
∆ aab
•
Immediately we push the symbol S onto the
STACK. STACK TAPE
S aab
STACK TAPE
• AB then we PUSH
We pop the S and aab B, PUSH
11
- PDA Conversion to CFG
•
We again feed back
into the central POP.
The production we
must now simulate is
a A → CC. This is STACK TAPE
done by popping the
CCB aab
A and following the
path PUSH C, PUSH
C.
STACK TAPE
CB aab
12
- PDA Conversion to CFG
•
We again feed
back into the
central POP. The
production we must
now simulate is a STACK TAPE
A → CC. This is
CCB aab
done by popping
the A and following
the path PUSH C,
PUSH C.
STACK TAPE
CB aab
13
- PDA Conversion to CFG
•
The next production
we must simulate is
another C a. Again
we POP C and
READ a.
STACK TAPE
B aab
•
This time when we STACK TAPE
enter the central ∆ aab
POP we simulate the
last production in the 14
- PDA Conversion to CFG
•
We now reenter the
POP, and we must
make sure that both
STACK and TAPE
are empty.
POP ∆ → READ3
→ ACCEPT
•
To accept a word
we must follow its
left- most derivation
from the CFG. If the 15
- PDA Conversion to CFG
•
Then at this point
in the corresponding
PDA-processing the
status of the
STACK and TAPE
should be STACK TAPE
ZWV ababbbaab
STACK TAPE
∆ ababbbaab
•
This process
continues until we
have derived the 16
- PDA Conversion to CFG
•
Example
S → AB
B → AB
B→a
A → BB
A→a
B→b
17
- Left- State STACK TAPE
most
derivatio
n
START ∆ baaab
S PUSH S S baaab
POP ∆ baaab
PUSH B B baaab
=> AB PUSHA AB baaab
POP B baaab
PUSH B BB baaab
⇒ BBB PUSH B BBB baaab
POP BB baaab
=>bBB READ3 BB baaab
POP B baaab
PUSH B BB baaab
18
- Babb READ3 BB baaab
POP B baaab
PUSH B BB baaab
BaBB Push A ABB baaab
POP BB baaab
BaBB READ1 B baaab
POP B baaab
⇒ bAAB READ2 B baaab
POP ∆ baaab
PUSH B B baaab
baaAB PUSH A AB baaab
Pop B baaab 19
- baaAB READ1 B baaab
POP ∆ baaab
baaab READ3 ∆ baaab
POP ∆ baaab
READ4 ∆ baaab
ACCEPT ∆ baaab
20
nguon tai.lieu . vn
