Problema da altura da estrela
# Problema da altura da estrela

O problema da altura da estrela na teoria das linguagens formais é a questão se todas linguagens regulares podem ser expressas usando Expressões regulares de Altura da estrela limitada, isto é, com uma profundidade aninhada da Estrela de Kleene limitada. Especificamente, um aninhamento profundo de um caminho é sempre suficiente? Se não, existe um Algoritmo para determinar quantas são requeridas? O problema foi levantado por Eggan (1963).

## Familias das linguagens regulares com altura de estrela ilimitadas

A primeira questão foi respondida na negativa em 1963, Eggan teve problemas de linguagens regulares de Altura da estrela n para todo n. Aqui, a altura da estrela h(L) de uma linguagem regular L é definida como a menor altura de estrela entre todas as expressões regulares representadas por L. As primeiras poucas linguagens encontradas por Eggan (1963) são descritas abaixo, através da atribuição de uma expressão regular para cada linguagem:
    ${\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}$
O principio da construção para essas expressões é o de que a expressão $e_{n+1}$ é obtida pela concatenação de duas cópias de $e_{n}$, apropriadamente renomeando as letras da segunda cópia usando novos símbolos do alfabeto, concatenando o resultado com outro símbolo novo do alfabeto, e depois envolvendo a expressão resultante com uma Estrela de Kleene. O restante, a parte mais difícil, é provar que para $e_{n}$ não existe um uma expressão regular equivalente de altura de estrela menor que n; a prova é dada em (Eggan 1963).
De qualquer maneira, os exemplos de Eggan usam um alfabeto grande, de tamanho 2$^n$-1 para a linguagem com altura de estrela n. Ele então perguntou se podemos também encontrar exemplos sobre alfabetos binários. Isto foi provado como verdadeiro pouco antes de Dejean & Schützenberger (1966). Seus exemplos podem ser descritos por uma definição indutiva de famílias de expressões regulares através do alfabeto binário $\{a,b\}$ da seguinte maneira - cf. Salomaa (1981):
    ${\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}$
Novamente, uma prova rigorosa é necessária para o fato de que $e_{n}$ não admite uma expressão regular equivalente de menor altura de estrela. Provas são dadas por (Dejean & Schützenberger 1966) e por (Salomaa 1981).

## Computando a altura da estrela de linguagens regulares

Diferentemente, a segunda questão se mostrou ser muito mais difícil, e a questão se tornou um famoso problema em aberto na teoria de linguagens formais por duas décadas (Brzozowski 1980). Por anos, houve apenas um pequeno progresso. As linguagens de grupo-puro foram as primeiras famílias interessantes de linguagens regulares para a quais o problema da altura da estrela foi provado ser decidível (McNaughton 1967). Porém o problema ficou em aberto por mais de 25 anos até ser resolvido por Hashiguchi, que em 1998 publicou um algoritmo para determinar a Altura da Estrela para qualquer linguagem regular. O algoritmo não foi até então totalmente prático, sendo de complexidade não-elementar. Para ilustrar o imenso consumo de recurso do algoritmo, Lombardy e Sakarovitch (2002) deu para todos os números:
Note que apenas o número $10^{10^{10}}$ tem 10 bilhões de zeros quando escrito na notação decimal, e está pronto por injustiça maior que o Número de átomos no universo.
Um algoritmo muito mais eficiente que o Procedimento de Hashiguchi foi planejado por Kirsten em 2005. Este algoritmo roda, por um Autômato finito não determinístico como entrada, com o double de espaço exponencial. Ainda o requerimento de recurso para este algoritmo ainda é muito além do que é viável.