Automate fini alternant
En informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation.
Le nom « alternant » est basé sur l'observation suivante : à condition d'autoriser les ε-transitions, deux types de conditions suffisent pour exprimer toutes les fonctions booléennes possibles sur les états : parmi les états atteints, au moins un est final ou bien tous sont finaux. Les choix varient donc entre un choix existentiel et un choix universel.
Les automates finis alternants sont utilisés pour la reconnaissance de mots infinis, en théorie des jeux, en model checking et en logique. Ils trouvent des applications aussi en apprentissage automatique.
Description
Il existe plusieurs classes d’automates finis qui diffèrent par leur « type de branchement » : les automates déterministes, automates non déterministes, les automates universels et automates alternants. Un automate déterministe traite un mot en passant d’un état au suivant selon la fonction de transition. L’automate accepte le mot à partir d’un état si l’état atteint après la lecture de accepte le suffixe . Un automate non déterministe qui lit la lettre dans un état peut en revanche passer en plusieurs états, déterminés par la relation de transition. L’automate accepte à partir de si l’un des états dans lesquels il peut passer après la lecture de accepte le suffixe . Une notion duale est celle d’automate universel. Comme pour un automate non déterministe, la relation de transition donne, pour un état et une lettre , un ensemble d’états; mais l’interprétation est ici que est accepté depuis l’état si tous les états atteints après la lecture de acceptent le suffixe .
Les automates alternants généralisent à la fois les automates non déterministes et les automates universels. Ils délèguent le rôle de tester l’acceptation du suffixe d'un mot à plusieurs états, en combinant leurs résultats par des conjonctions et disjonctions. Par exemple, une transition qui de l'état , en lisant la lettre , va vers l'expression , stipule que le mot est accepté depuis si son suffixe est accepté depuis ou à la fois depuis et .
Définition formelle
Un automate fini alternant est composé des données suivantes :
- un ensemble fini d'états ;
- un alphabet d'entrée ;
- un ensemble d'états terminaux ;
- , une fonction d'acceptation ;
- une fonction de transition.
L'état initial usuel dans les automates est remplacé par la fonction d'acceptation [1]. La fonction de transition associe à un état , à une lettre et à un vecteur d'états indicé par , une valeur booléenne. La fonction est étendue au mots par les deux propriétés suivantes :
- , où est la coordonnée d'indice de .
- , où est le vecteur .
Vue comme fonction opérant sur les vecteurs d'états, la fonction est donc étendue par
L'ensemble des mots acceptés par est
- ,
où
Ici est la fonction caractéristique de l’ensemble des états terminaux, représentée comme vecteur booléen. Un mot est donc accepté si la fonction booléenne prend la valeur 1 sur le vecteur qui lui est le vecteur booléens de tous les états pour lesquels le calcul de aboutit en un état final.
Exemples
Un premier exemple
On considère une automate à deux état et sur l'alphabet , l'ensemble des états terminaux est . La fonction de transition est donnée par
et la fonction d'acceptation est
Un exemple de calcul est alors
D'où
et le mot est donc accepté.
Un deuxième exemple
On considère un automate sur l’alphabet qui possède un seul état , état également final. La fonction de transition est donnée par :
et la fonction d'acceptation est . On voit que
- .
Le langage accepté par l'automate est donc :
- .
Cet automate a un seul état, alors que plus petit automate non déterministe qui reconnaît son langage a 2 états, et le plus petit automate déterministe a 4 états.
Propriétés et usages
Les automates finis non déterministes sont un cas particulier automates alternants; tout langage rationnel est, par conséquent, accepté par un automate alternant. Réciproquement, tout automate alternant peut être transformé en automate fini déterministe. Les automates finis alternants acceptent donc précisément les langages réguliers. Toutefois, un automate alternant peut être beaucoup plus petit. On peut gagner une exponentielle en passant d'un automate non déterministe à un automate alternant, et une double exponentielle en passant d'un automate déterministe à un automate alternant. La borne exacte dépend de la définition exacte des automates alternants. Ainsi, quand on autorise les négations dans les formules booléennes, il existe un automate fini alternant avec états pour lequel le plus petit automate fini déterministe requiert états. Quand on n’autorisent pas la négation, et alors la borne est [2].
Les automates alternants, sur les mots infinis, se définissent de manière analogue, en prenant comme condition d'acceptation par exemple la condition des automates de Büchi. Les automates alternants reconnaissent les mêmes langages de mots infinis que les automates de Büchi non déterministes, mais l’alternance peut rendre les automates exponentiellement plus petits.
Variations
Il existe diverses variations dans la définition des automates finis alternants. Ils ne modifient pas la puissance d'expression, mais peuvent être plus ou moins faciles à définir et plus ou moins faciles à mettre en œuvre[3]. C’est surtout la souplesse de la structure combinatoire d’une automate alternant qui est appréciée[3] : elle simplifie considérablement la traduction de spécifications de propriétés en automates, traduction qui est à la base des algorithmes de model checking. Les automates sont utilisés pour la spécification et la vérification de programmes. Quand un programme est défini relativement à un ensemble P de propositions, chaque état dans une exécution du programme correspond à une partie de P, à savoir à l'ensemble des propositions qui sont vraie dans cet état. Une exécution du programme définit ainsi un mot fini ou infini sur l’alphabet des parties de P, et le programme lui-même donne un ensemble de mots qui peut être défini par un automate. De même, la spécification d’un programme qui décrit les calculs possibles peut être vu comme un langage de mots sur l’alphabet des parties de P, et donc être défini par un automate. Ainsi, les questions sur les programmes se ramènent à des questions sur des automates. Par exemple, les questions de la satisfiabilité de la spécification et de la correction d’un programme se réduisent à des questions comme le test du vide, ou au problème d’inclusion pour les langages formels. La traduction de spécifications vers les automates prend en charge les aspects logiques, et déplace les difficultés combinatoires vers des problèmes de théorie combinatoire[3].
Une variante des automates consiste à ne pas autoriser les négations. C'est l'option retenue dans certains travaux sur l'apprentissage de langages réguliers[4].
Une variante dans la définition[2] même des automates consiste à introduire un état initial à la place de la fonction d'évaluation . La condition d'acceptation
est remplacée par la condition, plus contraignante en apparence, de
- .
Une autre variante, plus marquée, consiste à définir les automates alternants comme suit[5] : L'ensemble des états est divisé en deux parties, les états existentiels et universels . L'idée sous-jacente est que les transitions sortant d'un état de sont interprétées comme des transitions ou, et les transitions sortant d'un état de comme des transitions et. Syntaxiquement, ceci est la seule différence entre automates alternants et automates non déterministes.
Soit , avec un automate fini non déterministe usuel. Un mot est accepté à partir d'un état si est un état final et est le mot vide, ou alors si pour une lettre et un mot , et si soit :
- , et est accepté par au moins un des états dans , ou
- , et est accepté par tous les états dans .
Le langage accepté par un tel automate est l'ensemble des mots acceptés à partir de l’état initial.
La fonction de transition définie plus haut est remplacée par une fonction plus simple qui associe à un état et à une lettre une formule booléenne sur : Pour un état , une lettre , et , la fonction prend la valeur .
Notes et références
- ↑ Dans l'article fondateur Chandra, Kozen et Stockmeyer, 1981, il y a un état initial.
- ↑ a et b Chandra, Kozen et Stockmeyer, 1981.
- ↑ a b et c Kupferman et Vardi 2001.
- ↑ Angluin, Eisenstat et Fisman 2015.
- ↑ Kumar, Alternating automata.
Bibliographie
- Article fondateur
- Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, no 1, , p. 114-133 (DOI 10.1145/322234.322243).
- Autres articles
- Orna Kupferman et Moshe Y. Vardi, « Weak alternating automata and tree automata emptiness », Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98), , p. 224-233 (DOI 10.1145/276698.276748, lire en ligne)
- Orna Kupferman et Moshe Y. Vardi, « Weak alternating automata are not that weak », ACM Transactions on Computational Logic, vol. 2, no 3, , p. 408-429 (DOI 10.1145/377978.377993, lire en ligne)
- Dana Angluin, Sarah Eisenstat et Dana Fisman, « Learning regular languages via alternating automata », Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI 2015), , p. 3308-3314 (lire en ligne)
- Cours
- K. Narayan Kumar, « Alternating automata », Notes on Automata, Logic, Games and Algebra, Chennai Mathematical Institute, Chennai.
- Pascal Raiola, « Introduction to alternating finite automata », Automata Theory — Software Engineering, Informatik Universität Freiburg, .
Articles liés
v · m Automates finis et langages réguliers | |
---|---|
Articles généraux | |
Automates finis | |
Automates finis particuliers |
|
Langages réguliers | |
Des automates aux langages | |
Des langages aux automates | |
Minimisation | |
Équivalences |
Portail de l'informatique théorique