Question

What set of strings with symbols in the set \(\left\{ {{\bf{0,1,2}}} \right\}\) is represented by the regular expression \(\left( 2 \right){\left( {{\bf{0}} \cup \left( {{\bf{12}}} \right)} \right)^{\bf{*}}}\)?

The star height \({\bf{h(E)}}\) of a regular expression over the set \({\bf{I}}\) is defined recursively by

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

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

\({\bf{h}}\left( {\left( {{\bf{E}}1 \cup {\bf{E}}2} \right)} \right){\bf{ = h}}\left( {\left( {{\bf{E}}1{\bf{E}}2} \right)} \right){\bf{ = max}}\left( {{\bf{h}}\left( {{\bf{E1}}} \right){\bf{,h}}\left( {{\bf{E2}}} \right)} \right)\)if \({\bf{E}}1\) and \({\bf{E}}2\) are regular expressions;

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

Short answer

All strings that do not have a \(0\) immediately preceding a \(2\).

Step-by-step solution

Definition

Kleene closure of \({\bf{A}}\) : Set consisting of concatenations of any number of strings from \({\bf{A}}\) can be \({{\bf{A}}^{\bf{*}}}{\bf{ = }}\bigcup\limits_{{\bf{k = 0}}}^{{\bf{ + }}\infty } {{{\bf{A}}^{\bf{k}}}} \).

Using the definition of Kleene’s closure

By the definition of the Kleene closure: \({{\bf{2}}^{\bf{*}}}\) represents all strings consisting of zero or more \({\bf{2's}}\), while \({\bf{1}}{{\bf{2}}^{\bf{*}}}\) then represents all strings starting with a \(1\) followed by zero or more \({\bf{2's}}\).

\(0 \cup \left( {{\bf{1}}{{\bf{2}}^{\bf{*}}}} \right)\)then represent the set that contains the string \(0\) and all strings starting with a \(1\) followed by zero or more \({\bf{2's}}\). \({\left( {{\bf{0}} \cup \left( {{\bf{1}}{{\bf{2}}^{\bf{*}}}} \right)} \right)^{\bf{*}}}\) will then represent all strings that contain all \({\bf{2's}}\) directly after \(1\) or another \(2\), or equivalently, all strings that do not have a \(0\) immediately preceding a \(2\).

Therefore, the set \(\left( {{2^{\bf{*}}}} \right){\left( {0 \cup \left( {{\bf{1}}{{\bf{2}}^{\bf{*}}}} \right)} \right)^{\bf{*}}}\) then also contains all strings that do not have a \(0\) immediately preceding a \(2\).