Question

Express each of these sets using a regular expression.

1. The set containing all strings with zero, one, or two bits
2. The set of strings of two 0s, followed by zero or more 1s, and ending with a 0
3. The set of strings with every 1 followed by two 0s
4. The set of strings ending in 00 and not containing 11
5. The set of strings containing an even number of 1s

Short answer

(a): The regular expression for the given set is\({\bf{\lambda }} \cup {\bf{0}} \cup {\bf{1}} \cup {\bf{00}} \cup {\bf{01}} \cup {\bf{10}} \cup {\bf{11}}\).

(b): The regular expression for the given set is\({\bf{00}}1{\bf{*}}0\).

(c): The regular expression for the given set is \(\left( {100 \cup 0} \right){\bf{*}}\)

(d): The regular expression for the given set is\(\left( {{\bf{0}} \cup {\bf{10}}} \right){\bf{*}}\left( {{\bf{0}} \cup {\bf{1}}} \right)00\).

(e): The regular expression for the given set is\(\left( {10{\bf{*}}1 \cup 0} \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 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.

Step 2: Express the given sets using regular expressions

(a).

Given that, the set contains all strings with zero, one, or two bits.

Express the given set as a regular expression.

Since, all strings with zero, one or two bits are: \({\bf{\lambda ,0,1,00,01,10,11}}{\bf{.}}\)

And the regular expression is\({\bf{\lambda }} \cup {\bf{0}} \cup {\bf{1}} \cup {\bf{00}} \cup {\bf{01}} \cup {\bf{10}} \cup {\bf{11}}\).

Therefore, the required expression is\({\bf{\lambda }} \cup {\bf{0}} \cup {\bf{1}} \cup {\bf{00}} \cup {\bf{01}} \cup {\bf{10}} \cup {\bf{11}}\).

(b).

Given that, the set of strings of two 0s, followed by zero or more 1s and ending with a 0.

Express the given set as a regular expression.

Since all strings with zero or more 1s can be represented as\({\bf{1*}}\).

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

.

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

(c).

Given that, the set of strings with every 1 is followed by two 0s.

Express the given set as a regular expression.

The set of strings with every 1 followed by two 0s can only contain blocks 100 or single 0s.

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

Therefore, the required expression is\(\left( {100 \cup 0} \right){\bf{*}}\).

Express the given sets using regular expressions

(d).

Given that, the set of strings ending in 00 and not containing 11.

Express the given set as a regular expression.

Since the set of strings ending in 00 and not containing 11 consists of zero or more 0s or blocks 10s or end with a 1.

All strings with zero or more x’s can be written as \({\bf{x*}}\) and all the strings with zero or more 0s or blocks 10s are notated as\(\left( {{\bf{0}} \cup 10} \right){\bf{*}}\).

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

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

(e).

Given that, the set of strings containing an even number of 1s.

Express the given set as a regular expression.

Since the set of strings containing an even number of 1s consists of pairs of 11.

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

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