Usuário(a):Tomer Simis/Testes

O problema da altura da estrela na teoria das linguagens formais é a questão se todas linguagens regulares podem ser expressadas usando Expressões regulares de Altura da estrela limitada, isto é, com uma profundidade aninhada de 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 levando 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 em seguida, 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 um alfabeto fresco de símbolos, concatenando o resultado com outro alfabeto fresco de símbolos, e então ao redor da expressão resultante com uma Estrela de Kleene. O restante, a parte mais difícil, é provar para $e_{n}$ que não exista 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 uma largo Alfabeto, de tamanho 2ⁿ-1 para a linguagem com estrela de altura n. Ele então perguntou se nós podemos também encontrar através de alfabetos binários. Isto estava provado como vedade pequenamente antes de Dejean & Schützenberger (1966). Seus exemplos podem ser descritos por uma definição indutivo de famílias de expressões regulares através do alfabeto binário $\{a,b\}$ como seguesse–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}}$

De novo, 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).

Computado a altura da estrela de linguagens regulares

Em contraste, a segunda questão virada para ser muito mais difícil, e a questões se torna o famoso problema em aberto na teoria de linguagens formais por duas décadas (Brzozowski 1980). Por anos, aqui estava o pequeno progresso. O linguagens grupo-puro onde as primeiras famílias interessantes de linguagens regulares para o qual o problema da altura da estrela foi provado para ser decidívels (McNaughton 1967). Porém o problema gera remanescente aberto por mais de 25 anos antes de ser setado 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 o não Elementar complexo. Para ilustrar o imenso consumo 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 instancia, se L é aceita por um autômato de 4 estados de um loop de complexidade 3 (e com pequenos 10 elementos de transição monoid ), então um minorant 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 Automato 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.

See also

• 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 Automato finito determinístico

References

• 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 

[[Category:Automata theory]] [[Category:Formal languages]] [[Category:Theorems in discrete mathematics]]