• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q4E

Expert-verified
Found in: Page 875

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Show that these equalities hold.a) $${{\bf{\{ \lambda \} }}^{\bf{*}}}{\bf{ = \{ \lambda \} }}$$b) $${\bf{(A*)* = A*}}$$ for every set of strings A.

By the following steps, the equalities hold.

a)$${{\rm{\{ }}\lambda {\rm{\} }}^*} = {\rm{\{ }}\lambda {\rm{\} }}$$

b)$${\rm{(}}A*{\rm{)}}* = A*$$ for every set of strings A.

See the step by step solution

## Step 1: Definition.

Here AB represents the concatenation of A and B.

$$AB = {\rm{\{ }}xy|\,x \in A\,{\rm{and}}\,y \in B{\rm{\} }}$$

Kleene closure of A set consisting of the concatenation of any number of strings from A $${{\bf{A}}^{\bf{*}}}{\bf{ = }}\bigcup\limits_{k = 0}^{ + \infty } {{{\bf{A}}^{\bf{k}}}}$$

## Step 2: Proof$${{\bf{\{ \lambda \} }}^{\bf{*}}}{\bf{ = \{ \lambda \} }}$$.

(a)

$${{\rm{\{ }}\lambda {\rm{\} }}^2}$$Represent the concatenation of $${\rm{\{ }}\lambda {\rm{\} }}$$and $${\rm{\{ }}\lambda {\rm{\} }}$$. Thus

$${{\rm{\{ }}\lambda {\rm{\} }}^2} = \left\{ {xy|x \in {\rm{\{ }}\lambda {\rm{\} }}\,{\rm{and}}\,y \in {\rm{\{ }}\lambda {\rm{\} }} = {\rm{\{ }}\lambda \lambda {\rm{\} }} = {\rm{\{ }}\lambda {\rm{\} }}} \right\}$$

Similarly, we get $${{\rm{\{ }}\lambda {\rm{\} }}^n} = {{\rm{\{ }}\lambda {\rm{\} }}^{n - 1}}{\rm{\{ }}\lambda {\rm{\} }} = {\rm{\{ }}\lambda \lambda {\rm{\} }} = {{\rm{\{ }}\lambda {\rm{\} }}^2} = {\rm{\{ }}\lambda {\rm{\} }}\,form = 2,3,....$$

Using the definition of the Kleene closure, then

$${{\rm{\{ }}\lambda {\rm{\} }}^*} = \bigcup\limits_{k = 0}^{ + \infty } {{\lambda ^k}} = \bigcup\limits_{k = 0}^{ + \infty } \lambda = {\rm{\{ }}\lambda {\rm{\} }}$$

Hence, the equalities hold $${{\rm{\{ }}\lambda {\rm{\} }}^*} = {\rm{\{ }}\lambda {\rm{\} }}$$

## Step 3: Proof of $${{\bf{A}}^{\bf{*}}}{\bf{ = }}\bigcup\limits_{k = 0}^{ + \infty } {{{\bf{A}}^{\bf{k}}}}$$.

(b)

Now, by the definition of the Kleene closure

$${{\rm{(}}{A^*}{\rm{)}}^*} = \bigcup\limits_{k = 0}^{ + \infty } {{{{\rm{(}}{A^*}{\rm{)}}}^k}}$$

$${{\rm{(}}{A^*}{\rm{)}}^2}$$Represent the concatenation of$${A^*}$$and$${A^*}$$ Thus

$${{\rm{(}}{A^*}{\rm{)}}^2} = {\rm{\{ }}xy|x \in A\,and\,y \in {A^*}{\rm{\} }} = {A^*}$$

Similarly,$${{\rm{(}}{A^*}{\rm{)}}^n} = {{\rm{(}}{A^*}{\rm{)}}^{n - 1}}{A^*} = {A^*}{A^*} = {{\rm{(}}{A^*}{\rm{)}}^2} = {A^*}form = 2,3,....$$

Using the definition of the Kleene closure, then

$${\rm{(}}A*{\rm{)}}* = \bigcup\limits_{k = 0}^{ + \infty } {{{{\rm{(}}{A^*}{\rm{)}}}^k}} = \bigcup\limits_{k = 0}^{ + \infty } {{\rm{(}}{A^*}{\rm{)}}} A*$$

Therefore,$${\rm{(}}A*{\rm{)}}* = A*$$for every set of strings A.