Question

Find the star height of each of these regular expressions.

\(\begin{array}{l}{\bf{a) 0*1}}\\{\bf{b) }}{{\bf{0}}^{}}{{\bf{1}}^{}}\\{\bf{c) }}{\left( {{{\bf{0}}^{}}{\bf{01}}} \right)^{}}\\{\bf{d) }}\left( {{{\left( {{{\bf{0}}^{}}{\bf{1}}} \right)}^{}}} \right){\bf{*}}\\{\bf{e) }}\left( {{\bf{010*}}} \right)\left( {{\bf{1*01*}}} \right){\bf{*}}\left( {{\bf{(01)*(10)*}}} \right){\bf{*}}\\{\bf{f) }}\left( {\left( {\left( {\left( {\left( {{\bf{0*}}} \right){\bf{1}}} \right){\bf{*0}}} \right){\bf{*}}} \right){\bf{1}}} \right){\bf{*}}\end{array}\)

Short answer

\(\left( {\bf{a}} \right)\)The star height of the regular expression is \({\bf{1}}\).

\(\left( {\bf{b}} \right)\)The star height of the regular expression is \({\bf{1}}\).

\(\left( {\bf{c}} \right)\)The star height of the regular expression is \({\bf{2}}\).

\(\left( {\bf{d}} \right)\)The star height of the regular expression is \({\bf{3}}\).

\(\left( {\bf{e}} \right)\)The star height of the regular expression is \({\bf{2}}\).

\(\left( {\bf{f}} \right)\)The star height of the regular expression is \(4\).

Step-by-step solution

Definition

The star height of a regular expression is equal to the maximum nesting depth of the stars that occur in that expression. The height of the smallest star in a regular expression for a certain regular language is known as its star height.

Given:

\(h{\rm{(}}\emptyset {\rm{)}}{\bf{ }} = 0\)

\(h{\rm{(}}x{\rm{)}} = 0\)if \(x \in I\)

\(h\left( {{\rm{(}}x \cup y{\rm{)}}} \right) = h\left( {\left( {{E_1}{E_2}} \right)} \right) = \left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right)\)if \({E_1},{E_2}\) are regular expressions

\(h\left( {\left( {{E^*}} \right)} \right){\bf{ }} = h\left( E \right) + 1\)if \(E\) is a regular expression

Know that,

\(\begin{aligned}h\left( {\left( {{E_1}{E_2}} \right)} \right) &= {\rm{max}}\left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right)\\h\left( {\left( {{E^*}} \right)} \right) &= h\left( E \right) + 1\\h{\rm{(}}x{\rm{)}} &= 0\end{aligned}\)

Finding the star height

(a)

Given to find,

\(\begin{aligned}h\left( {0*1} \right){\bf{ }} &= {\rm{max}}\left( {h\left( {0*} \right),h\left( 1 \right)} \right)\\ &= {\rm{max}}\left( {h\left( 0 \right) + 1,h\left( 1 \right)} \right)\\ &= {\rm{max}}\left( {0 + 1,0} \right)\\ &= {\rm{max}}\left( {1,0} \right)\\ &= 1 \end{aligned}\)

Therefore, the star height of the regular expression is \({\bf{1}}\).

Discovering the star height

(b)

Given to find,

\(\begin{aligned}h\left( {0*1*} \right){\bf{ }} &= {\rm{max}}\left( {h\left( {0*} \right),h\left( {1*} \right)} \right)\\ &= {\rm{max}}\left( {h\left( 0 \right) + 1,h\left( 1 \right) + 1} \right)\\ &= {\rm{max}}\left( {0 + 1,0 + 1} \right)\\ &= {\rm{max}}\left( {1,1} \right)\\ &= 1 \end{aligned}\)

Know that

\(\begin{aligned}h\left( {\left( {E*} \right)} \right) &= h\left( E \right) + 1\\h\left( {\left( {{E_1}{E_2}} \right)} \right) &= {\rm{max}}\left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right)\\h\left( {\left( {E*} \right)} \right) &= h\left( E \right) + 1\\h\left( {\left( {{E_1}{E_2}} \right)} \right) &= {\rm{max}}\left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right)\\h\left( x \right) &= 0\end{aligned}\)

Therefore, the star height of the regular expression is \({\bf{1}}\).

Detecting the star height

(c)

Given to find,

\(\begin{aligned}h\left( {\left( {0*01} \right)*} \right) &= h\left( {0*01} \right) + 1\\ &= \max \left( {h\left( {0*} \right),h(01)} \right) + 1\\ &= \max (h(0) + 1,h(01)) + 1\\ &= {\rm{max}}\left( {h{\rm{(}}0{\rm{)}} + 1,{\rm{max}}\left( {h{\rm{(}}0{\rm{)}},h{\rm{(}}1{\rm{)}}} \right)} \right) + 1\\ &= {\rm{max}}\left( {0 + 1,{\rm{max(}}0,0{\rm{)}}} \right) + 1\\ &= {\rm{max(}}1,0{\rm{)}} + 1\\ &= 1 + 1\\ &= 2 \end{aligned}\)

Therefore, the star height of the regular expression is \({\bf{2}}\).

Locating the star height

(d)

Given to find,

\(\begin{aligned}\left. {h\left( {\left( {0*1} \right)*} \right)} \right) &= h\left( {\left( {0*1} \right)*} \right) + 1\\ &= h\left( {0*1} \right) + 1 + 1\\ &= {\rm{max}}\left( {h\left( {0*} \right),h{\rm{(}}1{\rm{)}}} \right) + 2\\ &= {\rm{max}}\left( {h{\rm{(}}0{\rm{)}} + 1,h{\rm{(}}1{\rm{)}}} \right) + 2\\ &= {\rm{max(}}0 + 1,0{\rm{)}} + 2\\ &= {\rm{max(}}1,0{\rm{)}} + 2\\ &= 1 + 2\\ & = 3 \end{aligned}\)

Therefore, the star height of the regular expression is \({\bf{3}}\).

Uncovering the star height

(e)

Given to find,

\(\begin{aligned}h\left( {\left( {010{*^*}} \right){{\left( {{1^*}01} \right)}^*}{{\left( {{{(01)}^*}{{(10)}^*}}\right)}^*}} \right)h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right) \\ &= \max \left( {h\left( {0100*} \right),h\left( {\left( {1*01*} \right)*\left( {(01)*(10)*}\right)*} \right)} \right) \\ h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left({{E_2}} \right)} \right) \\ &= \left. {\max \left( {\max \left( {h(01),h\left( {0*} \right)} \right),\max \left( {h\left( {1*01*} \right)*} \right)h\left( {\left( {(01)*(10)*} \right)*} \right)} \right)} \right) \\h\left( {\left( {E*} \right)} \right) &= h\left( E \right) + 1 \\ &= \max \left( {\max \left( {h(01),h(0) + 1} \right),\max \left( {h\left( {1*01*} \right) +1,h\left( {(01)*(10)*} \right) + 1} \right)} \right) \\ h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left({{E_2}} \right)} \right)andh(x) = 0 \\ &= \max \left( {\max \left( {\max \left( {h(0),h(1)} \right),0 + 1} \right),\max \left( {\max\left( {h\left( {1*} \right),h\left( {01*} \right)} \right) + 1} \right)} \right.,\left. {\left.{\max \left( {h\left( {(01)*} \right),h\left( {(10)*} \right)} \right) + 1} \right)} \right) \\h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left({{E_2}} \right)} \right)and \\ h(x) &= 0 = \max \left( {\max \left( {\max (0,0),1} \right),\max \left( {\max \left( {h\left( {1*}\right),\max \left( {h(0),h\left( {1*} \right)} \right)} \right) + 1,} \right.} \right.\left.{\left. {\max \left( {h\left( {(01)*} \right),h\left( {(10)*} \right)} \right) + 1} \right)} \right)\\\end{aligned} \)

Finding the star height

Given to find,

\(h\left( {\left( {E*} \right)} \right) = h{\rm{(}}E{\rm{)}} + 1\) and \(h{\rm{(}}x{\rm{)}} = 0\)

\(\begin{aligned} &= \max \left( {\max {\rm{(}}0,1{\rm{)}}} \right),\max \left( {\max \left( {h{\rm{(}}1{\rm{)}} + 1} \right)} \right),\max \left( {1,h{\rm{(}}1{\rm{)}} + 1} \right) + 1,\\\;\;\;\max \left( {h\left( {01} \right) + 1,h\left( {10} \right) + 1 + 1} \right)\\h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right)\\ &= \max \left( {1,\max \left( {\max 0 + 1,\max \left( {1,0 + 1} \right)} \right)} \right) + 1,\\\;\;\;\max \left( {\left( {\max (h\left( 0 \right),h\left( 1 \right)} \right) + 1,\max \left( {h\left( 1 \right),h\left( 0 \right)} \right) + 1 + 1} \right)\end{aligned}\)

Further, solve the above equation

\(\begin{aligned} h(x) = 0 \\ &= \max (1,\max (\max (1,\max (1,1)) + 1{\text{ }}\max (\max (0,0) + 1,\max (0,0) + 1) + 1)) \\ &= \max (1,\max (\max (1,1) + 1,\max (0 + 1,0 + 1) + 1)) \\ &= \max (1,\max (1 + 1,\max (1,1) + 1)) \\ &= \max (1,\max (2,1 + 1)) \\ &= \max (1,\max (2,2)) \\ &= \max (1,2) \\ &= 2 \\ \end{aligned} \)

Therefore, the star height of the regular expression is \({\bf{2}}\).

Detecting the star height

(f)

Given to find,

\(\begin{aligned} &=\left. {h\left( {\left( {\left( {\left( {\left( {0*} \right)1} \right)*0} \right)*}\right)1} \right)*} \right) \\ h\left( {\left( {E*} \right)} \right) &= h(E) + 1 \\ &=\left. { h\left( {\left( {\left( {\left( {0*} \right)1} \right)*0} \right)*} \right)1} \right) + 1 \\h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left({{E_2}} \right)} \right) \\ &= \left. { \max \left( {h\left( {\left( {\left( {0*}\right)1} \right)*0} \right)*} \right),h(1)} \right) + 1 \\ &= h\left( {\left( {E*} \right)}\right) = h(E) + 1 \\ and{\text{ }}h(x) &= 0 = \max \left( {h\left( {\left( {\left( {0*} \right)1} \right)*0}\right) + 1,0} \right) + 1 \\ h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left({h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right) \\ &=\left. { \max \left( {\max \left( {h\left( {\left( {0*} \right)1} \right)*} \right),h(0)} \right) + 1,0} \right) + 1 \\h\left({\left( {E*} \right)} \right) &= h(E) + 1 \\ &= \max \left( {\max \left( {h\left( {\left({0*} \right)1} \right) + 1,0} \right) + 1,0} \right) + 1 \\ h\left( {\left( {{E_1}{E_2}} \right)} \right) &= \max \left( {h\left( {{E_1}} \right),h\left( {{E_2}} \right)} \right) \\ &= \max \left({\max \left( {\max \left( {h\left( {0*} \right),h(1)} \right) + 1,0} \right) + 1,0} \right) + 1 \\ h\left({\left( {E*} \right)} \right) &= h(E) + 1 \\and{\text{ }}h(x) &= 0 = \max (\max (\max (h(0) +1,0) + 1,0) + 1,0) + 1 \\\end{aligned} \)

Discovering the star height

Let use the previous equation,

\(\begin{aligned} h(x) &= 0 \\ &= \max (\max (\max (0 + 1,0) + 1,0) + 1,0) + 1 \\ &= \max (\max (\max (1,0) + 1,0) + 1,0) + 1 \\ &= \max (\max (1 + 1,0) + 1,0) + 1 \\ & = \max (\max (2,0) + 1,0) + 1 \\ &= \max (2 + 1,0) + 1 \\ &= \max (3,0) + 1 \\ &= 3 + 1 \\ &= 4 \\ \end{aligned} \)

Therefore, the star height of the regular expression is \(4\).