Sketch of Solutions to Exercises

2.5.1

0||- -|| |- -- | q1,Op0 ----|- || 0|||- --- ---0 ||0 -| ||| |----0 1 -|- || |-- |||0| | --||q0,Op0|||-|q0,OOp1 q1,pO1 ||----- |- | ||| ------ ---- | 1 ||| 0 ---0---- |1 | |----- ||- q2,Op1 |----q2,pO0 ||--0 0 |||[source]

2.5.2 (a) Consider any regular language over an alphabet S. The following are regular languages.

L1 = {x|x is a non-empty string in S*}

L2 = L . L1

L3 = L2 /~\ L = Y(L)

(b) Let LM,q denote the language that the finite state automaton M accepts, when modified to have q as the only accepting state of M. Let Lq,M denote the language that the finite state automata M accepts, when modified to have q as the initial state of M.

Y(L1, L2) = U q,pLM1,qLM2,pLq,M1LMp,M2

2.5.3 Choose L = (ab)i|i > 0 and w = ambm in Y(L).

2.5.4 (a) Replace each transition rule in a finite state transducer that computes R, with a transition rule of the form

--||- O ------a/b-------|| O q p[source]

(b) If R is computable by M then Y(M ) is computable by

||||||| --- |- e/e -----|| q0O -- ---------- - - --||| Oo -||- - | --------- - M - -------- -- e/e -- Oo -- -||||||-[source]

(c) If R1 is computable by M 1, and R2 is computable by M 2, then Y(R1, R2) is computable by

|||||||||||||||| |||||||||||| -||| ||||||| -|| ||| --|| M |||||---|-e/e---|-|- M -- -- q0O1 1 -|||-| -- -- q02O 2 -- ||||| |||||- ||| |||- ||||||||||||||| ||||||||||[source]

(d) If R1 = R(M 1) and R2 = R(M 2) then Y(R1, R2) = R(M ) where

  1. Each state of M is a pair (q,p) of states, from M 1 and M 2 respectively.

  2. --|| O -------a/g------|| O q1,p1 q2,p2[source]

    in M if and only if for some b

    || a/b || -- --q1O ---------------- - q2O[source]

    in M 1 and

    || b/g || -- --p1O ---------------- - p2O[source]

    in M 2.

  3. (q0, p0) is the initial state of M if so are q0 and p0 in M 1 and M 2, respectively.

  4. (q, p) is an accepting state of M if so are q and p in M 1 and M 2, respectively.

2.5.5 Let R = {(e, e), (a, a), (aa, a)}. Then (aa, a) and (aa, aa) are in R.R .

2.5.6 |0|---- |0|-|- -|||||-- ||||||||| ||||-|- |||||||| |||-| ||- 1 ||--| |||- 0 ||--| ||- 1 ||-|| ||- -- -|| q0 |----- --|| q1 |----- --q0, q1|----- --q1, q2|-| ||||||| ||||||||| ||||||| ----|||-|||| ||| || ||| ---- || 1 || |||1 1| ----- ||0 ||||||||| |||||||||--- 1||||||| --- ----0||-- -| --| |-||-0,1 -|||q2 ||-- -|q0,q2--- q0,|q1,q2||||- ||||||| -|||||| |||| -|-||| 0[source]

See also prob 2.3.2

2.5.7

2.5.8 R(M ) = {(x, y)|x not in L(M )} U {(x, y)|x in L(M ), but (x, y) not in R(M )}