Regularidade de uma linguagem construída de uma linguagem regular

Question

Eu estou trabalhando através de perguntas tão dicas em idiomas regulares e deparamos com um problema que equivale a mostrar que a seguinte linguagem é regular, dado que $ a $ é Uma linguagem regular: $$ \ {x | \ existe n \ ge 0 \; Existe y \ em \; y= x ^ n \} $$

Eu tentei mostrar que isso é regular por uma contradição usando o myhill-nerode, assumindo que tem um índice infinito, e mostrando isso significa que $ a $ Deve ter infinito índice. No entanto, não consigo fazer essa prova para trabalhar, porque tomar representantes de cada classe me permite mostrar um número infinito de pares de elementos na $ a $ que não estão em a mesma classe, mas esses elementos não correspondem exclusivamente aos meus representantes, então não consigo mostrar que um elemento não está na mesma classe que infinitamente muitos outros.

No entanto, o livro parece indicar que a solução deve ser construção. Eu também posso facilmente ver a construção para um NFA se $ n $ foi corrigido, mas isso não parece oferecer nenhuma ajuda, pois isso faz com que os estados dependam de < span class="contentor de matemática"> $ n $ (usando tuplas de estados e, simultaneamente, mudando os estados uma vez).

Se alguém pudesse sugerir como construir o autômato necessário, isso seria muito útil.

Answer 1

Como você menciona, se $ n $ foi corrigido, então isso não é muito difícil de provar. Então, a ideia seria mostrar que, de fato, $ n $ pode ser limitado a-priori, dependendo apenas da $ Um $ , e não em $ x $ .

Para este fim, considere alguma palavra $ x \ in \ sigma ^ * $ e suponha $ x ^ m \ em um $ para alguma $ m $ . Deixe $ k $ Seja o número de estados em alguma dfa $ D $ para $ a $ (por exemplo, DFA mínimo). Suponha $ m> k $ , em seguida, existem $ 0 \ le eu tal que A corrida de $ D $ em $ x ^ i $ atinge o mesmo estado que na $ x ^ j $ . Mas isso implica que $ x ^ {m- {ji}} $ também é aceito por $ D $ .

Assim, é suficiente considerar $ n \ le k $ . Então você pode reescrever sua linguagem como $$ \ {x | \ existe n \ le k, \ x ^ n \ em A \} $$ E isso é regular.