CS 390 Solutions to Unit 11 Exercises

p. 166

4.44 (a): Since every prefix of strings of L can be bypassed by , the language accepted by M₁ is the set of all suffixes of all strings of L*.



4.28c)

\delta*(1,a) = {2,3}
\delta*(1,b) = @
\delta*(2,a) = {1}
\delta*(2,b) = @
\delta*(3,a) = @
\delta*(3,b) = {2,4}
\delta*(4,a) = {1,2,4}
\delta*(4,b) = @


4.28d)

\delta*(1,a) = {3,4, 5, 6}
\delta*(1,b) = {5}
\delta*(2,a) = {3}
\delta*(2,b) = @
\delta*(3,a) = @
\delta*(3,b) = {2}
\delta*(4,a) = {4,5,6}
\delta*(4,b) = {5}
\delta*(5,a) = {6}
\delta*(5,b) = {5}
\delta*(6,a) = @
\delta*(6,b) = @