Discrete Structures, Logic, and Computability, 4th Edition

Chapter 11

Section 11.1

1. a. {a, b}.

c. {a, Λ, b, bb, ... , bⁿ, ... }.

e. {a, b, ab, bc, abb, bcc, ... , abⁿ, bcⁿ, ... }.

2. a. a + b + c. c. ab* + ba*. e. Λ + a(bb)*. g. Λ + c*a + bc*. i. a*bc*.

3. 0 + 1(0 + 1)*.

4. a. (aa + ab + ba + bb)*. c. (a + b)*aba(a + b)*.

5. a. (ab)*. c. a (a + b)*.

6. a.

$\begin{array}{ll}b+a{b}^{*}+a{a}^{*}b+a{a}^{*}a{b}^{*}& =b+a{b}^{*}+a{a}^{*}(b+a{b}^{*})\\ =(\mathrm{\Lambda }+a{a}^{*})(b+a{b}^{*})\\ =a^{*}(b+a{b}^{*})\phantom{0000000000}(\mathrm{by}\left(\mathrm{11.1.1}\mathrm{e}\right)\end{array}$

c. By using property 7 of (11.1.1g) the subexpression (a + bb*a)* of the left side can be written (a*bb*a)*a*. So the left expression has the following form:

ab*a(a + bb*a)*b = ab*a(a*bb*a)*a*b.

Similarly, the subexpression (b + aa*b)* of the right side of the original equation can be written as b*(aa*bb*)*. So the right expression has the following form:

a(b + aa ...