250 Ji,t Theory of Computer Science
Proof Let L be accepted by a pda A = (QA' L, T, ~'i' qo, Zo, FA) by final
state and R by DFA M = (QM' L, ~'11' Po, F M )·
We define a pda M' accepting L () R by final state in such a way that M'
simulates moves of A on input a in L and changes the state of M using ~w. On
input A, M' simulates A without changing the state of M. Let
M ' = (QM X QA> L, r, 0, [Po, qo]. Zo, F M x FA)
where 0 is defined as follows:
o([p, q], a, X) contains ([P', q'], y) when ~"J(P, a) = p' and 0A(q, a, X)
contains (q', y). o([p, q], A, X) contains ([P, q'], y) when 0A(q, A. X)
contains (q', y).
To prove T(M ' ) = L () R we need an auxiliary result, i.e.
(7.39)
if and only if
(7.40)
We prove the 'only if part by induction on i (the number of steps). If
i =0, the proof is trivial (In this case, p =Po, q =qo, w =A and y= Zo). Thus
there is basis for induction. Let us assume that (7.39) implies (7.40) when the
former has i-I steps.
Let ([Po, qo]. ,v'a, Zo) ~ ([P, q], A, y). This can be split into ([Po, qo],
w'a, Zo) ~ ([p', q']. a, f3) fM; ([P, q], A, y), where w =w'a and a is in L
or a = A depending on the last move. By induction hypothesis, we have
(qo, w', Zo) ~ (q'. A, f3) and o'~IP', w') =p'. By definition of 0, ([P', q'],
a, f3) ~ ([P, q], A, y) implies (q', a, f3) ~ (q, A, y) and o,wCp', a) =p.
(Note: p' =p when a = A.) So, o,' i1
ZJ) r±- (q, A. y). So the result is true for i steps.
By the principle of induction the 'only if' part is proved.
We prove the 'if' part also by induction on i. It is trivial to see that there
is basis for induction.
Let us assume (7.40) with i-I steps. Assume that (qo, w, ZQ) ~ (q, A, y)
and ~"ho, w') = p. Writing w as w'a and taking oNIPo. w') as p', we get
(qo, }\/a, ZQ) ~ (q', a, {3) ~ (q, A, y). So, (qo, w', 2 0 ) iT (q', A, {3).
By induction hypothesis, we get ([Po, qo], w', Zo) ~ ([P', q'], A, {3).
Also, 0fw
Proof Let L be accepted by a pda A = (QA' L, T, ~'i' qo, Zo, FA) by final
state and R by DFA M = (QM' L, ~'11' Po, F M )·
We define a pda M' accepting L () R by final state in such a way that M'
simulates moves of A on input a in L and changes the state of M using ~w. On
input A, M' simulates A without changing the state of M. Let
M ' = (QM X QA> L, r, 0, [Po, qo]. Zo, F M x FA)
where 0 is defined as follows:
o([p, q], a, X) contains ([P', q'], y) when ~"J(P, a) = p' and 0A(q, a, X)
contains (q', y). o([p, q], A, X) contains ([P, q'], y) when 0A(q, A. X)
contains (q', y).
To prove T(M ' ) = L () R we need an auxiliary result, i.e.
(7.39)
if and only if
(7.40)
We prove the 'only if part by induction on i (the number of steps). If
i =0, the proof is trivial (In this case, p =Po, q =qo, w =A and y= Zo). Thus
there is basis for induction. Let us assume that (7.39) implies (7.40) when the
former has i-I steps.
Let ([Po, qo]. ,v'a, Zo) ~ ([P, q], A, y). This can be split into ([Po, qo],
w'a, Zo) ~ ([p', q']. a, f3) fM; ([P, q], A, y), where w =w'a and a is in L
or a = A depending on the last move. By induction hypothesis, we have
(qo, w', Zo) ~ (q'. A, f3) and o'~IP', w') =p'. By definition of 0, ([P', q'],
a, f3) ~ ([P, q], A, y) implies (q', a, f3) ~ (q, A, y) and o,wCp', a) =p.
(Note: p' =p when a = A.) So, o,' i1
ZJ) r±- (q, A. y). So the result is true for i steps.
By the principle of induction the 'only if' part is proved.
We prove the 'if' part also by induction on i. It is trivial to see that there
is basis for induction.
Let us assume (7.40) with i-I steps. Assume that (qo, w, ZQ) ~ (q, A, y)
and ~"ho, w') = p. Writing w as w'a and taking oNIPo. w') as p', we get
(qo, }\/a, ZQ) ~ (q', a, {3) ~ (q, A, y). So, (qo, w', 2 0 ) iT (q', A, {3).
By induction hypothesis, we get ([Po, qo], w', Zo) ~ ([P', q'], A, {3).
Also, 0fw