Problema de altura de estrela

O problema da altura das estrelas na teoria da linguagem formal é a questão de saber se todas as linguagens regulares podem ser expressas usando expressões regulares de altura de estrela limitada, ou seja, com uma profundidade de aninhamento limitada de estrelas de Kleene. Especificamente, uma profundidade de aninhamento de um é sempre suficiente? Caso contrário, existe um algoritmo para determinar quantos são necessários? O problema foi levantado por Eggan (1963).

Famílias de linguagens regulares com altura de estrela ilimitada

A primeira pergunta foi respondida negativamente quando, em 1963, Eggan deu exemplos de linguagens regulares de altura de estrela n para cada n. Aqui, a altura da estrela h(L) de uma linguagem regular L é definida como a altura mínima da estrela entre todas as expressões regulares que representam eu. As primeiras linguagens encontradas por Eggan (1963) são descritas a seguir, fornecendo uma expressão regular para cada linguagem:

$,,,, },,,,,,,,,,,,,,,,,,,,,),,,,,,,,,,,,),, },, },,,,$

O princípio da construção dessas expressões é a expressão $Não. e _{n+1}}$ é obtido por concatenar duas cópias de $Não. Erro:$, apropriadamente renomeando as letras da segunda cópia usando símbolos de alfabeto frescos, concatenando o resultado com outro símbolo de alfabeto fresco, e então ao redor da expressão resultante com uma estrela de Kleene. A parte restante, mais difícil, é provar que $Não. Erro:$ não há nenhuma expressão regular equivalente de altura da estrela menos do que n; uma prova é dada em (Eggan 1963).

No entanto, os exemplos de Eggan usam um alfabeto grande, de tamanho 2ⁿ-1 para a língua com altura estrela n. Ele assim perguntou se também podemos encontrar exemplos sobre alfabetos binários. Isto foi provado ser verdade pouco depois por Dejean & Schützenberger (1966). Seus exemplos podem ser descritos por uma família indutivamente definida de expressões regulares sobre o alfabeto binário. ${displaystyle {a,b}}$ como segue–cf. Salomaa (1981):

${bunderc_{2}&=(ab)^{2}e_{1}&=(ab)^{*e_{2}&=left(a(ab)^{*}bb(ab)^{(ab)}*right*$

Mais uma vez, uma prova rigorosa é necessária para o fato de que $Não. Erro:$ não admite uma expressão regular equivalente da altura da estrela inferior. As provas são dadas por (Dejean & Schützenberger 1966) e por (Salomaa 1981).

Calculando a altura da estrela de linguagens regulares

Em contraste, a segunda questão revelou-se muito mais difícil, e a questão tornou-se um famoso problema aberto na teoria da linguagem formal durante mais de duas décadas (Brzozowski 1980). Durante anos, houve apenas pouco progresso. As línguas de grupo puro foram a primeira família interessante de línguas regulares para a qual o problema da altura das estrelas provou ser decidível (McNaughton 1967). Mas o problema geral permaneceu em aberto por mais de 25 anos, até ser resolvido por Hashiguchi, que em 1988 publicou um algoritmo para determinar a altura da estrela de qualquer linguagem regular. O algoritmo não era nada prático, sendo de complexidade não elementar. Para ilustrar o imenso consumo de recursos desse algoritmo, Lombardy e Sakarovitch (2002) fornecem alguns números reais:

[O procedimento descrito por Hashiguchi] leva a computações que são de longe impossíveis, mesmo para exemplos muito pequenos. Por exemplo, se L é aceito por um autômato de 4 estado da complexidade do loop 3 (e com um pequeno monoide de transição de 10 elementos), então um muito baixo menor do número de línguas a serem testadas com L para a igualdade é: ${displaystyle left(10^{10^{10}}right)^{left(10^{10^{10}}right)^{left(10^{10^{10}}right)}}}$

—S. Lombardy e J. Sakarovitch, Altura Estrela de Linguagens reversíveis e Automata Universal, LATIN 2002

Observe que sozinho o número $Não. 10^{10^{10}}}$ tem 10 bilhões de zeros quando escrito em notação decimal, e já está de longe maior do que o número de átomos no universo observável.

Um algoritmo muito mais eficiente do que o procedimento de Hashiguchi foi desenvolvido por Kirsten em 2005. Este algoritmo é executado, para um determinado autômato finito não determinístico como entrada, dentro de um espaço exponencial duplo. No entanto, os requisitos de recursos deste algoritmo ainda excedem em muito as margens do que é considerado praticamente viável.

Este algoritmo foi otimizado e generalizado para árvores por Colcombet e Löding em 2008 (Colcombet & Löding 2008), como parte da teoria das funções de custo regulares. Foi implementado em 2017 no conjunto de ferramentas Stamina.