Condition d'infinitude du langage d'un automate à états finis

9

Il existe un théorème qui dit que:

Etant donné un automate à états finis ayant états, s'il existe une chaîne dont la longueur satisfait alors le langage accepté par l'automate est infini.nwn≤|w|≤2n-1

Je comprends la contrainte , mais je ne comprends pas pourquoi la contrainte est là.|w|≥n|w|≤2n-1

automata finite-automata rahul sharma
la source

Réponses:

5

Dans le pire des cas, votre NFA pourrait ressembler à ceci:

Le plus petit pour lequel il est garanti de boucler (l'obligeant à accepter un langage infini) a la taille .w2n−1

André Souza Lemos
la source
Quand je pars de q0 et ensuite quand je reviens à q0, cela signifie qu'il y a un cycle dans la machine. N'est-ce pas suffisant dans le pire des cas, pourquoi revenons-nous à l'étape finale à nouveau dans ce cas? D'après ce que je comprends de cette figure, nous allons pomper cette boucle une fois puis revenir à l'étape finale, donc cela signifie une fois que nous entrons dans la phase finale, nous supposons que ce n'est pas ma chaîne car elle est revenue à un autre état, mais une fois qu'elle revient à la phase finale, nous sommes sûrs que c'est notre chaîne car il y a une boucle qui a été pompé?
rahul sharma
www
Je comprends votre point, j'essaie juste de comprendre la limite supérieure de l'intervalle, pourquoi c'est 2n-1 et pourquoi pas 2n-x (x peut être n'importe quoi sauf 1) .Dans la figure ci-dessus, nous disons que la boucle est qo -q1 .... qn-q1 .... qn, à droite (la boucle max.)? Mais quand je suis à nouveau q0 (q0 ... aq, q0), cela ne signifie-t-il pas qu'il y a une boucle, donc le maximum devrait être n, pourquoi ajoutons-nous n-1 à n (ou pourquoi allons-nous à nouveau à l'état final) .J'ai du mal à obtenir ceci :(. la boucle maximale peut-elle être q0., q1, q2 ..qn, qn-1, qn-1..q0, quelque chose comme ça?
rahul sharma
2n-12n-X2n-12n-1
Je l'ai maintenant, juste un petit doute, supposons que j'ai 4 états dans ma machine, et j'ai lu la chaîne abc et j'ai atteint l'état final, puis j'ai lu d là et je suis revenu à l'état initial, puis à nouveau à l'état final, donc ma chaîne deviendra abcdabc. Comment puis-je diviser cela en lemme de pompage et obtenir y ^ i, où i = 1, pour montrer que y a été pompé une fois.?
rahul sharma
5

La condition supplémentaire vous permet d'écrire un algorithme simple - vérifier toutes les chaînes avec des longueurs dans cet intervalle - pour décider (en) finitude de la langue acceptée. Ainsi, vous obtenez une preuve que cette propriété est décidable (ce qui n'est pas le cas pour la plupart des modèles d'automates à puissance super régulière).

Raphael
la source
3

Le théorème complet énonce une équivalence plutôt qu'une implication :

nwn≤|w|≤2n-1

|w|≤2n-1

Yuval Filmus
la source