Considérez une machine à états finis comme d'habitude, mais à chaque transition, elle peut également mettre à jour un compteur entier en ajoutant ou en soustrayant un nombre. Disons, une fonction de transition de la forme passe au nouvel état p et ajoute k au compteur, où k ∈ Z (donc k peut être positif, négatif ou nul) .
Une chaîne est acceptée si l'état final et la valeur du compteur sont dans , où F est un ensemble fini de paires d'états et de valeurs de compteur.
Ce modèle est-il connu? Je n'ai trouvé aucune référence à cette extension particulière.
finite-automata
Chao Xu
la source
la source
Réponses:
En supposant que peut être n'importe quel entier, cela peut être formalisé comme un automate à guichet unique . Habituellement, ces automates acceptent l'état final lorsque son compteur est nul, mais nous pouvons facilement modéliser votre type d'acceptation si vous autorisez les transitions ϵ (qui ne consomment pas d'entrée). Si je ne me trompe pas, comme avec les automates à états finis, on peut se débarrasser du ϵ , mais c'est un résultat non trivial.k ϵ ϵ
Il existe plusieurs types d'automates à guichet unique. Dans la forme la plus générale, ils sont autorisés à tester si la valeur du compteur est égale à zéro. Les langues qu'ils acceptent sont un sous-ensemble strict des langues sans contexte.
Le modèle que vous recherchez probablement est appelé aveugle , il ne peut pas tester zéro, sauf comme test final d'acceptation à la fin du calcul.
la source
Ce modèle est une variante des automates pondérés, qui sont largement étudiés (bien qu'il y ait beaucoup de questions ouvertes à leur sujet). Vous pouvez commencer ici: Handbook of Weighted Automata .
Notez qu'ils sont parfois appelés "automates à distance" (bien que cela devienne moins courant).
la source