StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q4E

Expert-verifiedFound in: Page 875

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.

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}}}} \)

(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{\} }}\)

(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.

94% of StudySmarter users get better grades.

Sign up for free