(7.41)
(7.42)
(7.43)
(7.44)
(7.45)
(7.46)
(7.47)
(7.48)
(7.49)
(7.50)
(7.51)
(7.52)
Chapter 7: Pushdown Automata ~ 261
length, there is a middle symbol which need not be compared with any other
symbol. If w in L is of even length, the rightmost symbol of the first half is
the same as the leftmost symbol of the second half, The key idea of the
construction is to store the symbols in the first half (or the symbols lying to
the left of the middle of the input string) and matching them with the symbols
in the second half (or the symbols to right of the middle of the input string),
If there is no matching. the machine halts.
We define the pda M as follows:
M = ({qo, q], q:c}, {a, b}, {a, b, 2o}, 6, qo, zo, {qJ)
where 6 is defined by
6(qo, G, Zo) = {(qo, aZo), (qj, Zo)}
6(qo, b, Zo) = {(qQ, bZ o ), (q], Zo)}
6(qo, a. a) = {(qQ, aa), (ql> a)}
6(qo, b, a) = {(qo, ba), (q], a)}
6(qo. a. b) = {(qQ, ab), (qlo b)}
6(qQ' b. b) = {(qQ, bb), (q], b)}
6(qo, A. Zo)= {(q]. Zu)}
6(qo. A, a) = {(q)o n)}
6(qo, A. b) = {(q]. b)}
6(q], n. a)= {(qj. A)}
6(qlo b, b) = {(qlo A)}
6(q], A. Zo) = {(q:c. 2o)}
Obviously, M is a nondeterministic pda. (7.41)~(7.46) give us two
choices. The first choice can be used for storing the input symbol without
changing the state. (7.47)-(7.49) are used for indicating that the first half of
the input string is over: there is change of state in this case. The second choice
of (7.41 )-(7 .46) is used when w is a palindrome of odd length and the middle
symbol of w is reached: in this case. we ignore the middle symbol and make
no change in PDS. (7.50) and (7.51) are used to match symbols of the input
string (second half) and cancel the symbol in PDS when they match. (7.52)
is used to move to the final state q:c after reaching the bottom of PDS.
We can prove that L is accepted by M by final state. The reader can take
an odd palindrome and an even palindrome and check that the final state q:c
is reached.
EXAMPLE 7.16
Construct a deterministic pda accepting L = {w E {a, b} * I the number of a's
in HI equals the number of b's in w} by final state.
(7.42)
(7.43)
(7.44)
(7.45)
(7.46)
(7.47)
(7.48)
(7.49)
(7.50)
(7.51)
(7.52)
Chapter 7: Pushdown Automata ~ 261
length, there is a middle symbol which need not be compared with any other
symbol. If w in L is of even length, the rightmost symbol of the first half is
the same as the leftmost symbol of the second half, The key idea of the
construction is to store the symbols in the first half (or the symbols lying to
the left of the middle of the input string) and matching them with the symbols
in the second half (or the symbols to right of the middle of the input string),
If there is no matching. the machine halts.
We define the pda M as follows:
M = ({qo, q], q:c}, {a, b}, {a, b, 2o}, 6, qo, zo, {qJ)
where 6 is defined by
6(qo, G, Zo) = {(qo, aZo), (qj, Zo)}
6(qo, b, Zo) = {(qQ, bZ o ), (q], Zo)}
6(qo, a. a) = {(qQ, aa), (ql> a)}
6(qo, b, a) = {(qo, ba), (q], a)}
6(qo. a. b) = {(qQ, ab), (qlo b)}
6(qQ' b. b) = {(qQ, bb), (q], b)}
6(qo, A. Zo)= {(q]. Zu)}
6(qo. A, a) = {(q)o n)}
6(qo, A. b) = {(q]. b)}
6(q], n. a)= {(qj. A)}
6(qlo b, b) = {(qlo A)}
6(q], A. Zo) = {(q:c. 2o)}
Obviously, M is a nondeterministic pda. (7.41)~(7.46) give us two
choices. The first choice can be used for storing the input symbol without
changing the state. (7.47)-(7.49) are used for indicating that the first half of
the input string is over: there is change of state in this case. The second choice
of (7.41 )-(7 .46) is used when w is a palindrome of odd length and the middle
symbol of w is reached: in this case. we ignore the middle symbol and make
no change in PDS. (7.50) and (7.51) are used to match symbols of the input
string (second half) and cancel the symbol in PDS when they match. (7.52)
is used to move to the final state q:c after reaching the bottom of PDS.
We can prove that L is accepted by M by final state. The reader can take
an odd palindrome and an even palindrome and check that the final state q:c
is reached.
EXAMPLE 7.16
Construct a deterministic pda accepting L = {w E {a, b} * I the number of a's
in HI equals the number of b's in w} by final state.