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ⁿ-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:

“

[O procedimento descrito por Hashiguchi] lidera para computação que são injustamente impossíveis, até para pequenos exemplos. Por exemplo, se L é aceita por um autômato de 4 estados de um loop de complexidade 3 (e com pequenos 10 elementos de transição monoide), então um minorante bem pequeno para o número de linguagens para ser testado com L por igualdade é: $\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)}}.$

”

—  S. Lombardy e J. Sakarovitch, Altura da Estrela de Linguagens Reversíveis e Autômatos Universais, LATIN 2002

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.

Ver também

• Problema da Altura da Estrela generalizado
• Algoritmo Kleene — computa uma expressão regular (usualmente de uma altura de estrela não mínima)para uma linguagen dada por um Autómato finito determinístico

Referências

• McNaughton, Robert (1967). «The Loop Complexity of Pure-Group Events». Information and Control. 11 (1–2): 167–176. doi:10.1016/S0019-9958(67)90481-0 
• Hashiguchi, Kosaburo (1982). «Regular languages of star height one». Information and Control. 53 (2): 199–210. doi:10.1016/S0019-9958(82)91028-2 
• Hashiguchi, Kosaburo (1988). «Algorithms for Determining Relative Star Height and Star Height». Information and Computation. 78 (2): 124–169. doi:10.1016/0890-5401(88)90033-8 
• Lombardy, Sylvain; Sakarovitch, Jacques (2002). «Star Height of Reversible Languages and Universal Automata» (PDF). Springer. 5th Latin American Symposium on Theoretical Informatics (LATIN) 2002, vol. 2286 of LNCS 
• Kirsten, Daniel (2005). «Distance Desert Automata and the Star Height Problem». RAIRO - Informatique Théorique et Applications. 39 (3): 455–509. doi:10.1051/ita:2005027 
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177