Question

For each of these regular expressions find a regular expression that represents the same language with minimum star height.

\(\begin{array}{l}{\bf{a) }}\left( {{\bf{0*1*}}} \right){\bf{*}}\\{\bf{b) }}\left( {{\bf{0}}\left( {{\bf{01*0}}} \right){\bf{*}}} \right){\bf{*}}\\{\bf{c) }}\left( {{\bf{0*}} \cup {\bf{(01)*}} \cup {\bf{1*}}} \right){\bf{*}}\end{array}\)

Short answer

a) The regular expression with star height expression is \({\bf{(0}} \cup {\bf{1)*}}\).

b) The regular expression with star height expression is \({\bf{(0(01*0))}}*\) already has minimum star height.

c) The regular expression with star height expression is \({\bf{(0}} \cup {\bf{1)*}}\).

Step-by-step solution

Step \({\bf{1}}\): Definition

Kleene closure of \(A\): Set consisting of concatenations of any number of strings from \(A\)can be

\(A* = \bigcup\limits_{k = 0}^{ + \infty } {{A^k}} \)

Finding the regular expression

(a)

\(\left( {0*1*} \right)*\)By the definition of the Kleene closure, \(0*\) represents a string of zero or more \(0{\bf{ }}'s\) and \(1*\) represents a string of zero or more \(1{\bf{ }}'s\).

This then implies that \(\left( {0*1*} \right)*\) represents any concatenation of \(0{\bf{ }}'s\) and \(1{\bf{ }}'s\), which are all possible bit strings. It can also notate the set of all bit strings as \({\bf{(0}} \cup {\bf{1)}}*\) which has the minimum star height of \(1\) (as it cannot represent the set of all bit strings without using the Kleene closure).

Therefore, the regular expression with star height expression is \({\bf{(0}} \cup {\bf{1)*}}\)

Detecting the regular expression

(b)

\({\bf{(0(01*0))}}*\)By the definition of the Kleene closure, \(1*\) represents a string of zero or more \(1{\bf{ }}'s\).

\(01*0\)then represents all strings starting and ending with zeros, while \(\left( {01*0} \right)*\) then represents all strings in which the \({{\rm{(}}^{}}'{\rm{)'}}s\) are separated by at least two zeros.

\(\left( {0\left( {0*0} \right)} \right)*\)then represents all strings in which the \(1{\bf{ }}'s\) are separated by at least three zeros.

\({\bf{(0(01*0))}}*\)has height \(3\) due to the expression containing two Kleene closures. It is not possible to represents the set of all strings in which the \(1{\bf{ }}'s\) are separated by at least three zeros with \(1\) or no Kleene closures and it is mentioned that the regular expression already has least star height.

Therefore, the regular expression with star height expression is \({\bf{(0(01*0))}}*\) already has minimum star height.

Discovering the regular expression

(c)

\(\left( {0* \cup \left( {01} \right)* \cup *} \right)*\)

By the definition of the Kleene closure, \(0*\) represents a string of zero or more \(0{\bf{ }}'s\) and \(1*\) represents a string of zero or more \(1{\bf{ }}'s\).

This then implies that \(\left( {0* \cup \left( {01} \right)* \cup *} \right)*\) represents any concatenation of \(0{\bf{ }}'s\) and \(1{\bf{ }}'s\), which are all possible bit strings. It can also notate the set of all bit strings as \({\bf{(0}} \cup {\bf{1)*}}\) which has the minimum star height of \(1\) (as it cannot represent the set of all bit strings without using the Kleene closure).

Therefore, the regular expression with star height expression is \({\bf{(0}} \cup {\bf{1)*}}\).