Chapter 7. Pushdown Automata
In
the earlier chapters, we have considered the simplest type of
automaton, namely, the FSA. We have seen that a FSA has finite amount
memory and hence cannot accept type 2 languages like {anbn|n
≥ 1}. In this chapter, we consider a class of automata, the pushdown
automata, which accept exactly the class of context-free (type 2)
languages. The pushdown automaton is a finite automaton with an
additional tape, which behaves like a stack. We consider two ways of
acceptance and show the equivalence between them. The equivalence
between context-free grammars (CFG) and pushdown automata is also
proved.
7.1. The Pushdown Automaton
Let us consider the following language over the alphabet Σ = {a, b, c}: L = {anbmcn|n, m
≥ 1}. To accept this, we have an automaton which has a finite control
and the input tape which contains the input. Apart from these, there is
an additional pushdown tape which is like a stack of plates placed on a
spring. Only the top most plate is visible. Plates can be removed from
top and added at the top only. In the following example, we have a red
plate and a number of blue plates. The machine is initially is q0 state and initially a red plate is on the stack. When it reads a it adds a blue plate to the stack and remains in state q0. When it sees the b, it changes to q1. In q1, it reads b’s without manipulating the stack. When it reads a c it goes to state q2 and removes a blue plate. In q2 state, it proceeds to read c’s and whenever it reads a c it removes a blue plate. Finally, in q2
state without reading any input it removes the red plate. The working
of the automaton can be summarized by the following table.
| State | Top plate | Input | ||
| a | b | c | ||
| q0 | red | add blue plate remain in state q0 | — | — |
| blue | add blue plate remain in state q0 | go to q1 | — | |
| q1 | red | — | — | — |
| blue | — | remain in state q1 | go to q2 remove the plate | |
| q2 | red | without waiting for input remove red plate | ||
| blue | — | — | remain in q2 remove the plate | |
7.2. Equivalence between Acceptance by Empty Store and Acceptance by Final State
In this section, we show that acceptance by empty store and acceptance by final state are equivalent.
Theorem 7.1
L is accepted by a PDA M1 by empty store, if and only if L is accepted by a PDA M2 by final state.
Proof (i) Let L be accepted by a PDA M2 = (K, Σ, Γ, δ2, q0, Z0, F) by final state. Then construct M1 as follows:
δ mappings are defined as follows:
The first move makes M1 go to the initial ID of M2 (except for the X0 in the pushdown store). Using the second set of mappings M1 simulates M2. When M2 reaches a final state using mapping 3, M1 goes to the erasing state qe and using the set of mappings 4, entire pushdown store is erased.
Hence, if w is accepted by M2, it will be accepted by M1. On the other hand, if M1 is presented with an input, the first move it can make is using mapping 1 and once it goes to state qe, it can only erase the pushdown store and has to remain in qe
only. Hence, mapping 1 should be used in the beginning and mapping 3
and 4 in the end. Therefore, mapping 2 will be used in between and the
sequence of moves will be as in Equation (7.1).
Hence,
(ii) Next, we prove that if L is accepted by M1 by empty store, it will be accepted by M2 by final state. Let M1 = (K, Σ, Γ, δ1, q0, Z0, φ). Then, M2 is constructed as follows:
Two more states q0′ and qf are added to the set of states K. q0′ becomes the new initial state and qf becomes the only final state. One more pushdown symbol X0 is added which becomes the new initial pushdown symbol. The δ mappings are defined as follows:
Mapping 1 makes M2 go to the initial ID of M1 (except for the X0 in the pushdown store). Then using mapping 2, M2 simulates M1. When M1 accepts by emptying the pushdown store, M2 has X0 left on the pushdown store. Using mapping 3, M2 goes to the final state qf.
The moves of M2 in accepting an input w can be described as follows:
It is not difficult to see that w is accepted by M2, if and only if w is accepted by M1.
It should be noted that X0 is added in the first part for the following reason. M2 may reject an input w by emptying the store and reaching a nonfinal state. If X0 were not there, M1 while simulating M2 will empty the store and accept the input w. In the second part, X0 is added because for M2
to make the last move and reach a final state, a symbol in the pushdown
store is required. Thus, we have proved the equivalence of acceptance
by empty store and acceptance by final state in the case of
non-deterministic PDA.
|
7.3. Equivalence of CFG and PDA
In this section, we show the equivalence of CFG and non -deterministic PDA.
Theorem 7.2
If L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty store.
Proof Let L be generated by G = (N, T, P, S). Then M = ({q}, T, N ∪ T, δ, q, S, φ) can be constructed to accept L(G). δ is defined as follows.
If A → α is a rule in P, δ(q, ε, A) contains (q, α). For each α in T, δ(q, a, a) contains (q, ε).
To see that L(G) = N(M), we note that M simulates a leftmost derivation in G. Suppose
Equation 7.2
is a leftmost derivation in G. M uses an ε-move
if the top pushdown symbol is a non-terminal and reads a true input
symbol if the top pushdown symbol is the same as that input symbol and
pops it off.
(i) We show if w ∊ L(G), then w ∊ N(M).
Consider the derivation in Equation (7.2). Suppose αi can be written as xiγi where xi is the terminal prefix string and γi begins with a non-terminal.
We show by induction on i, the number of steps of derivations in G, that
|
Problems and Solutions
| 1. | Let L = {aibjck|i, j, k ≥ 1 and i + j = k}
| |
| Solution. |
| |
| 2. | Find a PDA for L = {x ∊ {a, b, c}*||x|a + |x|b = |x|c}. | |
| Solution. | This example is slightly different from the previous one as one can have interleaving occurrences of a’s, b’s and c’s.
The transitions are:
| |
| 3. | Give an example of a finite language that cannot be recognized by any one-state PDA that accepts via final state. | |
| Solution. | L = {abc}
Reason
If abc is accepted in state q0, then ab, a are also accepted in q0.
| |
| 4. | Let L = {anbncmdm|n, m ≥ 1}. Find a PDA that accepts L. | |
| Solution. | M = ({q0, q1, q2, q3, q4}, {a, b, c, d}, {a, c, $}, δ, q0, $, {q4})
Transitions are:
This machine accepts L by empty stack. Taking q4 as the final state L is accepted by final state also.
| |
| 5. | Design a PDA to accept the following language.
| |
| Solution. |
| |
| 6. | Find a PDA for
| |
| Solution. |
where δ is given by:
δ(q0, 0, $) contains (q0, X$)
δ(q0, 0, X) contains (q0, X X)
δ(q0, 1, $) contains (q0, X$)
δ(q0, 1, X) contains (q0, X X)
δ(q0, 0, $) contains (q1, $)
δ(q0, 0, X) contains (q1, X)
δ(q1, 0, X) contains (q1, ε)
δ(q1, 1, X) contains (q1, ε)
δ(q1, 1, $) contains (q2, ε)
Acceptance is by empty stack. We can also look at it as acceptance by final state by taking q2 as the final state.
|
No comments:
Post a Comment