Sketch of Solutions to Exercises

3.5.1

(a) Replace each transition rule of the form (q, a, b, p, g, r) with a transition rule of the form (q,r,b,p,g,a).

(b) Consider any two pushdown transducers M 1 and M 2. The relation R(M 1) U R(M 2) is computable by a pushdown transducer M that consists of two components M 1' and M 2. Each accepting computation of M starts at M 1' and ends at M 2.

M 1' is a component similar to M 1. The only difference is that the accepting states of M 1 are nonaccepting states in M 1'.

The transition of M from M 1' to M 2 is made from those states of M 1' that correspond to the accepting states of M 1. Upon the transition from M 1' to M 2 the pushdown memory is emptied.

(c) Consider any pushdown transducer M . The reversal of R(M ) is computed by a pushdown transducer M rev that is derived from M with the following modifications.

  1. M rev has the states of M plus two new states, say, q0 and qf . All the states of M are nonaccepting states in M rev.
  2. q0 is the initial state of M rev. While in q0 the pushdown transducer stores nondeterministically some string in the pushdown store.

    The string being stored corresponds to the content of the pushdown store of M upon halting in an accepting configuration or the give input.

  3. M rev nondeterministically can move from qo to any of the states that corresponds to any accepting state of M .

    The state being chosen corresponds to the state of M upon halting in an accepting configuration on the given input.

  4. qf is the accepting state of M rev. M rev can reach qf on empty pushdown store from the state that corresponds to the initial state of M .
  5. Each production rule of the form (q, a, b, p, g, r) is simulated by a sequence of moves that starts at state p, ends at state q, reads arev, writes rrev, pops g, and pushes b.
3.5.2 Choose L1 = {aibi|i > 0} and L2 = {cjdj|j > 0} and use the pumping lemma with the string w = amcmbmdm in Y(L1, L2).

3.5.3

|| | b|| || |||-|| a| ||||| a|e| ||||| e| |||-|| --||||q ,p ||e--a-|q|,p |||-|||-q| ,p|Z0--|Z0|q ,p ||- |||0|||0|| |||1|||1|-||||||1|||2||| |||2|||2|| | b|| | | |a |e | | | e|| |b|| |Z0 Z0 a |e || || -||||-|||| | -|||||||||| -||||-|||| ||q0,p2||-|||-|q2,p1||-- ||q0,p1||- b|| ||| | a |e | | | | | | |a|| |a|| a|| | |e|a e|a e|a | | || ||||| ||||||||| ||q|,p ||-||---------------||q ,p |||- |||2|||0|| | -|||1|||0||- e| Z0 Z0[source]

3.5.4

e|| || a|e e| -|-- | a e|- -||- b|| - -| --||- a|e ||| --||-- -||--||||||||||||- -| -q-|- | p|- |||| e|| ||| || Z0 |Z0 || || a|| || |a |a || || || ||bb|b || || || || --|||||||- - || -|qtrap|--| -||- |- | | ||| a|| b|| e e, e e[source]

M eof without mixed states.

| e|| e|| a |e a|e -|-- | -|-| -||| b|| ---- ----- ||a||e|||||||---- --||--q--|--||||||||||||-p | -|||- | -|-- ||| e|| | | | || Z0 |Z0 | | ||| |ae|e | b|| be|e | | |b||b |||| || || --||| ae|a --||||||| - ------------|- -| -qa-- -|qtrap|-|| ||| ||||- |- || | -|| a| b e| e,e |e[source]

e|| || a|e || ae|e ||||--||||| b|| |||||||||- |||-||||||||||| ----a|e------ |||||||||||| --| ||------ -----|||| ||- -||q, accept ||||------ ----------|p, reject |-- |||||||||||||| ------| |||||||||||| ||- --- e|| | - -- --- Z0 |Z0 | - - |--- | -- - b|| --- | - - e||e ---||||||| | - - || --||| ||||| | | b||- -aee --||-| q0,reject -| | b|| e|e- - ||||||||||||||| |b |b -- - ||| a|| | - - |||e||a | - - ||| | - -- ||| | -||| | |||| || |||||||||||||||| ea|a |||||||||||||||||||-|| a || b || -| -------------------|-| --|-e|e e|e |||qa,accept||||- |||qtrap, reject|||||--| , ||||||| |||-||||[source]