Condição para infinitude da linguagem de um autômato de estado finito

9

Existe um teorema que diz que:

Dado um autômato de estado finito com estados, se existe uma string cujo comprimento satisfaz , o idioma aceito pelo autômato é infinito.nWn≤|w|≤2n−1

Eu entendo a restrição , mas não entendo por que a restrição está lá.|w|≥n|w|≤2n−1

automata finite-automata rahul sharma
fonte

Respostas:

5

Na pior das hipóteses, seu NFA pode ficar assim:

O menor para o qual é garantido um loop (forçando-o a aceitar uma linguagem infinita) tem tamanho 2 n - 1 .W2n-1 1

André Souza Lemos
fonte
Quando começo de q0 e depois quando voltei para q0, isso significa que há um ciclo na máquina. Na pior das hipóteses, não é suficiente, por que estamos voltando à fase final novamente? Pelo que entendi a partir desta figura, vamos bombear esse loop uma vez e depois voltar à fase final, então isso significa Uma vez que entramos no estágio final, assumimos que esta não é a minha string, pois voltou a outro estado, mas quando ela volta ao estágio final, temos certeza de que essa é a nossa string, pois há algum loop que foi bombeado?
Rahul sharma
Estamos tentando provar algo sobre o autômato, a saber, que ele aceita uma linguagem infinita. Na forma como a prova é formulada, uma string é conjeturada, cujo tamanho é assumido dentro de um determinado intervalo. Obviamente, se o autômato tiver um loop, a sequência w existe. O que acontece é que, se é impossível encontrar w dentro desse intervalo, a máquina não pode ser como a da figura. Ou não possui loops ou não possui estados finais. www
André Souza Lemos
Eu entendo o seu ponto. Estou apenas tentando entender o limite superior do intervalo, por que é 2n-1 e por que não 2n-x (x pode ser qualquer coisa, exceto 1). Na figura acima, podemos dizer que o loop é qo -q1 .... qn-q1 .... qn, certo (o loop máximo)? Mas quando estou q0 novamente (q0 ... aq, q0), isso não significa que há um loop, Então, o máximo deve ser n, por que estamos adicionando n-1 a n (ou por que estamos indo para o estado final novamente). Estou tendo dificuldades para obter isso :(. o loop máximo pode ser q0., q1, q2 ..qn, qn-1, qn-1..q0, algo assim?
rahul sharma
O limite superior é porque não fica pior que isso. 2 n - x é menor que 2 n - 1 , e acabei de mostrar um autômato que precisa de 2 etapas n - 1 . Não existe um que precise de mais (e faça o trabalho), mas há um que precisa dessa quantia. 2n−12n−x2n−12n−1
André Souza Lemos
Entendo que eu tenho 4 estados na minha máquina.E eu li a string abc e cheguei ao estado final e depois li lá e voltei ao estado inicial e depois ao estado final novamente, então minha string se tornará abcdabc. Como posso transformar isso em lema de bombeamento e obter y ^ i, onde i = 1, para mostrar que y foi bombeado uma vez.?
Rahul sharma
5

A condição adicional permite que você escreva um algoritmo direto - verifique todas as strings com comprimentos nesse intervalo - para decidir (in) a finitude do idioma aceito. Assim, você obtém uma prova de que essa propriedade é decidível (o que não é para a maioria dos modelos de autômatos com energia super-regular).

Rafael
fonte
3

O teorema completo indica uma equivalência e não uma implicação :

O idioma aceito por uma NFA do estado é infinito se, e somente se, contiver uma palavra w cujo tamanho satisfaça n ≤ | w | ≤ 2 n - 1 .nwn≤|w|≤2n−1

A condição extra torna o teorema mais forte .|w|≤2n−1

Yuval Filmus
fonte