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 $w$ 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 $w=a_{1}a_{2}\cdots a_{k}$ en passant d’un état au suivant selon la fonction de transition. L’automate accepte le mot $w$ à partir d’un état $q$ si l’état atteint après la lecture de $a_{1}$ accepte le suffixe $v=a_{2}\cdots a_{k}$. Un automate non déterministe qui lit la lettre $a$ dans un état $q$ peut en revanche passer en plusieurs états, déterminés par la relation de transition. L’automate accepte $w$ à partir de $q$ si l’un des états $q_{1},\ldots ,q_{m}$ dans lesquels il peut passer après la lecture de $a_{1}$ accepte le suffixe $v$. Une notion duale est celle d’automate universel. Comme pour un automate non déterministe, la relation de transition donne, pour un état $q$ et une lettre $a$, un ensemble d’états; mais l’interprétation est ici que $w$ est accepté depuis l’état $q$ si tous les états $q_{1},\ldots ,q_{m}$ atteints après la lecture de $a_{1}$ acceptent le suffixe $v$.

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 $q$, en lisant la lettre $a$, va vers l'expression $q_{1}\lor (q_{2}\land q_{3})$ , stipule que le mot $w=av$ est accepté depuis $q$ si son suffixe $v$ est accepté depuis $q_{1}$ ou à la fois depuis $q_{2}$ et $q_{3}$.

Définition formelle

Un automate fini alternant ${\mathcal {A}}=(Q,\Sigma ,q_{0},F,g)$ est composé des données suivantes :

• $Q$ un ensemble fini d'états ;
• $\Sigma$ un alphabet d'entrée ;
• $F\subseteq Q$ un ensemble d'états terminaux ;
• $h:2^{Q}\to \{0,1\}$, une fonction d'acceptation ;
• $g\colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}$ une fonction de transition.

L'état initial usuel dans les automates est remplacé par la fonction d'acceptation $h$. La fonction de transition $g$ associe à un état $q$, à une lettre $a$ et à un vecteur d'états $v$ indicé par $Q$, une valeur booléenne. La fonction $g$ est étendue au mots par les deux propriétés suivantes :

• $g(q,\varepsilon ,v)=v_{q}$, où $v_{q}$ est la coordonnée d'indice $q$ de $v$.
• $g(q,ax,v)=g(q,a,g(x,v))$, où $g(x,v)$ est le vecteur $g(q,x,v)_{q\in Q}$.

Vue comme fonction opérant sur les vecteurs d'états, la fonction $g:\Sigma ^{*}\times \{0,1\}^{Q}\to \{0,1\}^{Q}$ est donc étendue par

$g(\varepsilon ,v)=v$

$g(ax,v)=g(a,g(x,v))$

L'ensemble des mots acceptés par ${\mathcal {A}}$ est

$L({\mathcal {A}})=\{w\mid h(g(w,f))=1\}$,

où

$f(q)={\begin{cases}1&{\text{si }}q\in F\\0&{\text{sinon}}\end{cases}}$

Ici $f$ est la fonction caractéristique de l’ensemble $F$ des états terminaux, représentée comme vecteur booléen. Un mot $w$ est donc accepté si la fonction booléenne $h$ prend la valeur 1 sur le vecteur $g(w,f)$ qui lui est le vecteur booléens de tous les états $q$ pour lesquels le calcul de $w$ aboutit en un état final.

Exemples

Un premier exemple

On considère une automate à deux état $q_{1}$et $q_{2}$sur l'alphabet $\Sigma =\{a,b\}$, l'ensemble des états terminaux est $F=\{q_{2}\}$. La fonction de transition est donnée par

• $g(a,(q_{1},q_{2}))=(q_{1}\lor {\overline {q_{2}}},{\overline {q_{1}}}\land {\overline {q_{2}}})$

• $g(b,(q_{1},q_{2}))=(q_{1}\land {\overline {q_{2}}},{\overline {q_{1}}}\lor q_{2})$

et la fonction d'acceptation est

$h(q_{1},q_{2})={\overline {q_{1}}}\lor q_{2}$

Un exemple de calcul est alors

${\begin{aligned}g(ba,f)&=g(b,g(a,f))\\&=g(b,g(a,(0,1))\\&=g(b,(0\lor {\bar {1}},{\bar {0}}\land {\bar {1}}))=g(b,(0,0))\\&=(0\land {\bar {0}},{\bar {0}}\lor 0)=(0,1)\\\end{aligned}}$

D'où

$h(g(ba,f))=h((0,1))={\bar {0}}\lor 1=1$

et le mot $ba$ est donc accepté.

Un deuxième exemple

On considère un automate ${\mathcal {A}}$ sur l’alphabet $\Sigma =\{a,b\}$ qui possède un seul état $Q=\{q\}$, état également final. La fonction de transition est donnée par :

$g(a,q)={\overline {q}}$

$g(b,q)=0$

et la fonction d'acceptation est $h(q)=q$. On voit que

$g(a,1)=0,\ g(aa,1)=g(a,0)=1,g(b,1)=g(b,0)=0,g(bw,1)=g(bw,0)=0$.

Le langage accepté par l'automate est donc :

$L({\mathcal {A}})=\{a^{2n}\mid n\geq 0\}\cup \{a^{2n+1}bw\mid n\geq 0,w\in \Sigma ^{*}\}$.

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 $n$ états pour lequel le plus petit automate fini déterministe requiert $2^{2^{n}}$ états. Quand on n’autorisent pas la négation, et alors la borne est $2^{2^{n}/{\sqrt {n}}}$.

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. C’est surtout la souplesse de la structure combinatoire d’une automate alternant qui est appréciée : 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.

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.

Une variante dans la définition même des automates consiste à introduire un état initial $q_{0}$ à la place de la fonction d'évaluation $h$. La condition d'acceptation

$h(g(w,f))=1$

est remplacée par la condition, plus contraignante en apparence, de

$g(q_{0},w,f)=1$.

Une autre variante, plus marquée, consiste à définir les automates alternants comme suit : L'ensemble $Q$ des états est divisé en deux parties, les états existentiels $Q_{\exists }$ et universels $Q_{\forall }$. L'idée sous-jacente est que les transitions sortant d'un état de $Q_{\exists }$ sont interprétées comme des transitions ou, et les transitions sortant d'un état de $Q_{\forall }$ comme des transitions et. Syntaxiquement, ceci est la seule différence entre automates alternants et automates non déterministes.

Soit ${\mathcal {A}}=(Q,\Sigma ,s,F,\delta )$, avec $Q=Q_{\exists }\cup Q_{\forall }$ un automate fini non déterministe usuel. Un mot $w$ est accepté à partir d'un état $q$ si $q$ est un état final et $w$ est le mot vide, ou alors si $w=av$ pour une lettre $a$ et un mot $v$, et si soit :

• $q\in Q_{\exists }$, et $v$ est accepté par au moins un des états dans $\delta (q,a)$, ou
• $q\in Q_{\forall }$, et $v$ est accepté par tous les états dans $\delta (q,a)$.

Le langage accepté par un tel automate est l'ensemble des mots acceptés à partir de l’état initial.

La fonction de transition $g\colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}$ définie plus haut est remplacée par une fonction plus simple $g\colon Q\times \Sigma \to \mathbb {B} (Q)$ qui associe à un état $q$ et à une lettre $a$ une formule booléenne sur $Q$ : Pour un état $q$, une lettre $a$, et $\delta (q,a)=\{q_{1},\ldots ,q_{k}\}$, la fonction $g$ prend la valeur $g(q,a)={\begin{cases}q_{1}\lor q_{2}\lor \cdots \lor q_{k}&{\text{si }}q\in Q_{\exists }\\q_{1}\land q_{2}\land \cdots \land q_{k}&{\text{si }}q\in Q_{\forall }\end{cases}}$.

Bibliographie

Article fondateur

• Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ janvier 1981, 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),‎ 1998, 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, n^o 3,‎ 2001, 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),‎ 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, 2013.

Articles liés

• Model checking
• Machine de Turing
• Automate sur les mots infinis