A estrela Kleene de uma linguagem unitária infinita sempre produz uma linguagem regular

Seja , onde e para todos os .$L = \{a^n \mid n \ge 0\}$$a^0 = \epsilon$$a^n = a^{n-1}a$$n \ge 1$

Assim consiste em sequências de de todos os comprimentos, incluindo uma sequência de comprimento . Deixe ser qualquer subconjunto infinito de . Preciso mostrar que sempre existe um DFA para reconhecer .$L$$a$$0$$L_2$$L$$L_2^*$

Se é um subconjunto finito, é muito óbvio, pois seria um DFA e, portanto, pelo fechamento de Kleene, seria reconhecido por um DFA. Mas não consigo obtê-lo para um subconjunto infinito, pois pode não ser expresso como DFA quando, por exemplo, os comprimentos das strings são primos.$L_2$$L_2$$L_2^*$$L_2$

Suponha que haja duas palavras no idioma cujos comprimentos sejam relativamente primos. Seja esses comprimentos e . Sabemos (veja isso ) que, adicionando esses números um ao outro repetidamente, podemos obter qualquer número maior que . Então, se e são e , podemos escrever qualquer número maior do que como uma combinação linear de e . O que isso significa para nós: consiste em alguma linguagem finita arbitrária (regular, como todas as línguas finitas), em união com a linguagem$x$$y$$(x - 1)(y - 1) - 1$$x$$y$$13$$7$$72$$7$$13$$L_2^*$$\{w \in a^* \mid |a| > (x-1)(y-1)-1\}$. Esse idioma é regular, pois é o idioma de todas as palavras com um conjunto finito de palavras removido. Como é uma união de idiomas regulares, também deve ser regular.$L_2^*$

Se todas as palavras em tiverem comprimentos que compartilhem o maior fator comum (chame esse fator comum de ), repita o argumento acima, mas em vez de usar comprimentos de string, use comprimentos de string divididos por . Nesse caso, será a concatenação de uma linguagem finita arbitrária (regular) e da linguagem , também regular (já que $ (a ^ m) ^ * é regular e estamos removendo dele muitas palavras finitas).$L_2^*$$m$$m$$L_2^*$$\{w \in (a^m)^* \mid |w| > m^2[(x/m - 1)(y/m - 1) - 1]\}$

Por exemplo, suponha que todas as palavras em tenham um GCF de 2 e o idioma contenha as palavras e . Temos , e , que são relativamente primos. Portanto, sabemos que podemos obter qualquer palavra cujo comprimento seja múltiplo de se o comprimento for maior que concatenando e .$L$$a^4$$a^{10}$$m = 2$$x/m = 4/2 = 2$$y/m = 10/2 = 5$$m$$m^2[(x/m - 1)(y/m - 1) - 1] = 2^2[(2 - 1)(5 - 1) - 1] = (4)(3) = 12$$a^4$$a^{10}$