Question

Express each of these sets using a regular expression.

1. The set of strings of one or more 0s followed by a 1
2. The set of strings of two or more symbols followed by three or more 0s
3. The set of strings with either no 1 preceding a 0 or no 0 preceding a 1
4. The set of strings containing a string of 1s such that the number of 1s equals 2 modulo 3, followed by an even number of 0s

Short answer

1. Therefore, the regular expression for the given set is\({\bf{00*1}}\).
2. Hence, the regular expression for the given set is \(\left( {0 \cup 1} \right)\left( {0 \cup 1} \right)\left( {0 \cup 1} \right){\bf{*00}}00{\bf{*}}\)
3. So, the regular expression for the given set is\(0{\bf{*}}1{\bf{*}} \cup 1{\bf{*}}0{\bf{*}}\).
4. Accordingly, the regular expression for the given set is\(11\left( {111} \right){\bf{*}}\left( {00} \right){\bf{*}}\).

Step-by-step solution

General form

Regular expressions (Definition):

The regular expressions over a set I are defined recursively by:

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

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

The symbol xis 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 Aand Bare 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.

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

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

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

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

Step 2: Express the given sets using regular expressions

(a).

Given that,the set ofstrings of one or more 0s followed by a 1.

Express the given set as regular expression.

And the regular expression is\({\bf{00*1}}\).

So, the required expression is\({\bf{00*1}}\).

(b).

Given that,the set of strings of two or more symbols followed by three or more 0s.

Express the given set as a regular expression.

And the regular expression is\(\left( {0 \cup 1} \right)\left( {0 \cup 1} \right)\left( {0 \cup 1} \right){\bf{*00}}00{\bf{*}}\).

Hence, the required expression is\(\left( {0 \cup 1} \right)\left( {0 \cup 1} \right)\left( {0 \cup 1} \right){\bf{*00}}00{\bf{*}}\).

Express the given sets using regular expressions

(c).

Given that, the set of strings with either no 1 preceding a 0 or no 0 preceding a 1.

Express the given set as a regular expression.

And the regular expression is\(0{\bf{*}}1{\bf{*}} \cup 1{\bf{*}}0{\bf{*}}\).

Accordingly, the required expression is \(0{\bf{*}}1{\bf{*}} \cup 1{\bf{*}}0{\bf{*}}\).

(d).

Given that, the set of strings containing a string of 1s such that the number of 1s equals 2 modulo 3, followed by an even number of 0s.

Express the given set as regular expression.

And the regular expression is\(11\left( {111} \right){\bf{*}}\left( {00} \right){\bf{*}}\).

Therefore, the required expression is\(11\left( {111} \right){\bf{*}}\left( {00} \right){\bf{*}}\).