CS 390 Solutions to Unit 10 Exercises

pp. 156 - 160

4.2 (b) $\delta^{*} (1,a) = \cup_{p \in \delta^{*} (1, \Lambda) } \delta (p,a)$
$\delta^{*} (1,\Lambda) = \{ 1 \}$.
Hence $\delta^{*} (1,a) = \delta (1,a) = \{1, 2 \}$
Hence $\delta^{*} (1,ab) = \cup_{p \in \delta^{*} (1,a) } \delta (p, b) = \cup_{p \in \{1,2\} } \delta (p, b)$
= $\delta (1, b) \cup \delta (2, b)$
= $\{ 1, 3 \}$

4.3 $\delta^{*} (q,a) = \cup_{p \in \delta^{*} (q, \Lambda) } \delta (p,a)$ and $\delta^{*} (q, \Lambda) = \{ q \}$.
Hence $\cup_{p \in \delta^{*} (q, \Lambda) } \delta (p,a) = \delta (q,a)$
Hence $\delta^{*} (q,a) = \delta (q,a)$



4.15 (a) $a(ab + baa)^{*}(aba)^{*}(aa+bab)a$
(c) $( (a^{*}b + ab^{*})ab )^{+}$

Your answer may be different than these answers.
To check the equivalence automatically go to <a href="../exp15/index.html"><r><font color="blue">Regular Expression Equivalence Checker</font></r></a>

4.16 (a) $\Lambda ( \{2,3\} ) = \{ 2, 3, 5 \}$
(b) $\Lambda ( \{1 \} ) = \{ 1, 2, 5 \}$
(d) Since $\Lambda ( \{1 \} ) = \{ 1, 2, 5 \}$, $\delta^{*} (1,b) = \Lambda ( \delta (1,b) \cup \delta (2,b) \cup \delta (5,b))$ = $\Lambda ( \{ 6, 7 \} )$ = $\{ 1, 2, 5, 6, 7 \}$.
Hence $\delta^{*} (1,ba) = \Lambda ( \delta (1,a) \cup \delta (2,a) \cup \delta (5,a) \cup \delta (6,a) \cup \delta (7,a) )$ = $\Lambda ( \{ 3, 5 \} )$ = $\{ 3, 5 \}$.