• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Deutsch (DE)
Deutsch (UK)
Deutsch (US)

Americas

Europe

Answers without the blur. Sign up and see all textbooks for free! → Illustration

Q4E

Expert-verified
Discrete Mathematics and its Applications
Found in: Page 875
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

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

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later
Illustration

Short Answer

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 by Step Solution

TABLE OF CONTENTS :
TABLE OF CONTENTS

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.

Most popular questions for Math Textbooks

Given a deterministic finite-state automaton \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\), use structural induction and the recursive definition of the extended transition function f to prove that \({\bf{f }}\left( {{\bf{s, x y}}} \right){\bf{ = f }}\left( {{\bf{f }}\left( {{\bf{s ,x}}} \right){\bf{, y}}} \right)\)for all states \({\bf{s}} \in {\bf{S}}\)and all strings\({\bf{x}} \in {\bf{I}}*{\bf{andy}} \in {\bf{I}}*\).

Describe the set of strings defined by each of these sets of productions in EBNF.

\(\begin{array}{c}\left( {\bf{a}} \right){\bf{string :: = L + D?L + }}\\{\bf{L :: = a }}\left| {{\bf{ b }}} \right|{\bf{ c }}\\{\bf{D :: = 0 | 1}}\\\left( {\bf{b}} \right){\bf{string :: = signD + |D + }}\\{\bf{sign :: = + | - }}\\{\bf{D :: = 0 | 1|2|3|4|5|6|7|8|9}}\\\left( {\bf{c}} \right){\bf{string :: = L*}}\left( {{\bf{D + }}} \right){\bf{?L* }}\\{\bf{L :: = x |y }}\\{\bf{D :: = 0 | 1}}\end{array}\)

Construct a Moore machine that determines whether an input string contains an even or odd number of 1s. The machine should give 1 as output if an even number of 1s are in the string and 0 as output if an odd number of 1s are in the string.

Give production rule in Backus-Naur form for an identifier if it can consist of

a. One or more lower case letters.

b. At least three but no more than six lowercase letter

c. One to six uppercase or lowercase letters beginning with an uppercase letter.

d. A lowercase letter, followed by a digit or an underscore, followed by three or four alphanumeric characters (lower or uppercase letters and digits.)

A context-free grammar is ambiguous if there is a word in \({\bf{L(G)}}\) with two derivations that produce different derivation trees, considered as ordered, rooted trees.

Show that the grammar \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) with \({\bf{V = }}\left\{ {{\bf{0, S}}} \right\}{\bf{,T = }}\left\{ {\bf{0}} \right\}\), starting state \({\bf{S}}\), and productions \({\bf{S}} \to {\bf{0S,S}} \to {\bf{S0}}\), and \({\bf{S}} \to 0\) is ambiguous by constructing two different derivation trees for \({{\bf{0}}^{\bf{3}}}\).
Icon

Want to see more solutions like these?

Sign up for free to discover our expert answers
Get Started - It’s free

Recommended explanations on Math Textbooks

Decision Maths

Read explanation

Calculus

Read explanation

Probability and Statistics

Read explanation

Statistics

Read explanation

Mechanics Maths

Read explanation

Geometry

Read explanation

Pure Maths

Read explanation

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.