Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 13: Q2E (page 887)

Describe in words the strings in each of these regular sets.

  1. \(00{\bf{1*}}\)
  2. \(\left( {01} \right){\bf{*}}\)
  3. \(01 \cup 00{\bf{1*}}\)
  4. \(0\left( {11 \cup 0} \right){\bf{*}}\)
  5. \(\left( {1{\bf{0}}1{\bf{*}}} \right){\bf{*}}\)
  6. \(\left( {0{\bf{*}} \cup 1} \right)11\)

Short Answer

Expert verified
  1. Therefore, the regular sets in words are all bit strings containing two 0s followed by zero or more 1s.
  2. Hence, the regular sets in words are all bit strings consisting of zero or more repetitions of 01.
  3. So, the regular set in words is the string 01 and all bit strings containing two 0s followed by zero or more 1s.
  4. Accordingly, the regular sets in words are all bit strings starting with a 0 that contains all 1s in pairs.
  5. Thereafter, the regular sets in words are all bit strings in which all 0s are separated by at least one 1 and in which the string starts with 10 or.
  6. Henceforth, the regular sets in words are the bit string 111 and all bit strings consisting of zero or more 0s followed by 11.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

General form

Regular expressions (Definition):

The regular expressions over a set are defined recursively by:

The symbol \(\emptyset \)is a regular expression.

The symbol \({\bf{\lambda }}\)is a regular expression.

The symbol x is a regular expression whenever\({\bf{x}} \in {\bf{I}}\).

The symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are regular expressions whenever A and B are regular expressions.

Rules of regular expression represent a set:

\(\emptyset \) represents the empty set, that is, the set with no strings.

\({\bf{\lambda }}\)represents the set\(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string.

x represents the set \(\left\{ {\bf{x}} \right\}\) containing the string with one symbol x.

(AB) represents the concatenation of the sets represented by A and by B.

\(\left( {{\bf{A}} \cup {\bf{B}}} \right)\) represents the union of the sets represented by A and by B.

\({\bf{A*}}\)represents the Kleene closure of the sets represented by A.

02

Step 2: Describe the regular sets in words

(a).

Given that, \(00{\bf{1*}}\).

\({\bf{1*}}\)represents a string with any number of 1s.

Then, \(00{\bf{1*}}\) represents all strings containing two 0s followed by zero or more 1s.

Therefore, the sets in words are all bit strings containing two 0s followed by zero or more 1s.

(b).

Given that, \(\left( {01} \right){\bf{*}}\).

\(0{\bf{1}}\)represents the one string 01.

Then, \(\left( {01} \right){\bf{*}}\) represents all bits strings consisting of zero or more 1s.

Hence, the sets in words are all bit strings consisting of zero or more repetitions of 01.

(c).

Given that,\(01 \cup 00{\bf{1*}}\).

\(01\)is represents only a bit string 01.

\({\bf{1*}}\)represents a string with any number of 1s.

\(00{\bf{1*}}\)represents all strings containing two 0s followed by zero or more 1s.

Then, \(01 \cup 00{\bf{1*}}\)represents the string 01 and all bit strings containing two 0s followed by zero or more 1s.

So, the set in words is the string 01 and all bit strings containing two 0s followed by zero or more 1s.

03

Describe the regular sets in words

(d).

Given that, \(0\left( {11 \cup 0} \right){\bf{*}}\)

\({\bf{1}}1\)is represents only a bit string 11.

\(0\)is represents only a bit string 0.

The union \(11 \cup 0\) then contains two bits strings: 11or 0.

Then, \(\left( {11 \cup 0} \right){\bf{*}}\) represents all bit strings made up out of 0s or 11s, which are all bit strings in which the 1s come in pairs.

Finally, \(0\left( {11 \cup 0} \right){\bf{*}}\) represents all bit strings with a 0 that contains all 1s in pairs.

Accordingly, the sets in words are all bit strings starting with a 0 that contains all 1s in pairs.

(e).

Given that\(\left( {1{\bf{0}}1{\bf{*}}} \right){\bf{*}}\)

\(101{\bf{*}}\)represents all strings starting with a 10 followed by zero or more.

Then, \(\left( {1{\bf{0}}1{\bf{*}}} \right){\bf{*}}\) represents all bit strings in which all0s are separated by at least one 1 and in which the string starts with 10.

Henceforth, the sets in words are all bit strings in which all 0s are separated by at least one 1 and in which the string starts with 10 or\({\bf{\lambda }}\).

(f).

Given that,\(\left( {0{\bf{*}} \cup 1} \right)11\).

\(0{\bf{*}}\)represents a string with any number of 0s.

\(\left( {{\bf{0*}} \cup {\bf{1}}} \right)\)represents the bit string 1 and all possible strings containing zero or more 0s.

Then, \(\left( {0{\bf{*}} \cup 1} \right)11\) represents the bit string 111 and all bit strings consisting of zero or more 0s followed by 11.

Thereafter, the set in words is the bit string 111 and all bit strings consisting of zero or more 0s followed by 11.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

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}}\) and \({\bf{S}} \to 0\) is unambiguous.

Suppose that A is a subset of\({{\bf{V}}^{\bf{*}}}\)where V is an alphabet.Prove or disprove each of these statements.

\(\begin{array}{l}{\bf{a)}}\,\,{\bf{A}} \subseteq {{\bf{A}}^{\bf{2}}}\\{\bf{b)}}\,\,{\bf{if}}\,{\bf{A = }}{{\bf{A}}^{\bf{2}}}{\bf{,then}}\,{\bf{\lambda }} \in {\bf{A}}\\{\bf{c)}}\,\,{\bf{A\{ \lambda \} = A}}\\{\bf{d)}}\,\,{{\bf{(}}{{\bf{A}}^{\bf{*}}}{\bf{)}}^{\bf{*}}}{\bf{ = }}{{\bf{A}}^{\bf{*}}}\\{\bf{e)}}\,\,{{\bf{A}}^{\bf{*}}}{\bf{A = }}{{\bf{A}}^{\bf{*}}}\\{\bf{f)}}\,\,\left| {{{\bf{A}}^{\bf{n}}}} \right|{\bf{ = }}{\left| {\bf{A}} \right|^{\bf{n}}}\end{array}\)

Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of

\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)

Show that a set is generated by a regular grammar if and only if it is a regular set.

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}}*\).
See all solutions

Recommended explanations on Math Textbooks

Pure Maths

Read Explanation

Decision Maths

Read Explanation

Applied Mathematics

Read Explanation

Statistics

Read Explanation

Geometry

Read Explanation

Probability and Statistics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free