Encontre a altura estrela de cada uma destas expressões regulares.
b) 0^{*} 1^{*}

Passo 1

O enunciado pede para encontrar a altura estrela da expressão regular 0^{*}1^{*}. A altura estrela de uma expressão regular é a profundidade máxima de aninhamento do operador Kleene star. Usamos a definição recursiva:
h(\emptyset)=0,\quad h(a)=0,\quad h(E+F)=\max\{h(E),h(F)\},\quad h(EF)=\max\{h(E),h(F)\},\quad h(E^{*})=1+h(E).

Passo 2

Na expressão 0^{*}1^{*} há duas aplicações de Kleene star, mas nenhuma delas está aninhada em outra. Logo,
h(0^{*})=1+h(0)=1+0=1,
h(1^{*})=1+h(1)=1+0=1,
e como a concatenação toma o máximo, temos
h(0^{*}1^{*})=\max\{h(0^{*}),\,h(1^{*})\}=1.

Resposta

A altura estrela de 0^{*}1^{*} é 1.

Exercícios de Livros Relacionados