Automate fini inambigu

Un automate fini inambigu à n+1 états reconnaissant les mots qui ont un a en position n depuis la fin. Un automate déterministe équivalent a au moins $2^{n}$ états

En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers.

Le nombre d'états d'un automate inambigu peut être exponentiellement plus petit qu'un automate déterministe équivalent. En contre-partie, certains problèmes sont plus difficiles à résoudre pour les automates inambigus que pour les automates déterministes. Par exemple, partant d'un automate A, un automate A' reconnaissant le complément du langage accepté par A se construit en temps linéaire si A est déterministe, mais il n'est pas connu s'il peut être calculé en temps polynomial si A est inambigu.

Définition

Un automate fini non déterministe ${\mathcal {A}}=(Q,i,{\mathcal {F}},T)$, où ${\mathcal {F}}$ est l'ensemble des transition, $i$ l’état initial et $T$ l'ensemble des états terminaux, est dit inambigu si, pour tout mot $w=a_{1}\cdots a_{n}$ reconnu par l'automate, il existe un seul chemin réussi d'étiquette $w$, donc un seul chemin

$c=(i,a_{1},p_{1})(p_{1},a_{2},p_{2})\cdots (p_{n-1},a_{n},t)$, avec $t\in T$.

Exemple

Soit $L_{n}=A^{*}aA^{n-1}$ l'ensemble des mots sur l'alphabet binaire $A=\{a,b\}$ dont la lettre en position $n$ depuis la fin est un $a$. Les figures ci-contre montrent un automate inambigu reconnaissant ce langage pour n=2, et un automate déterministe pour ce même langage.

Automate inambigu pour le langage $L_{2}$.

Automate déterministe pour le langage $L_{2}$.

L'automate déterministe minimal acceptant $L_{n}$ a $2^{n}$ états, alors que l’automate inambigu pour le même langage n'a que $n+1$ états.

Propriétés

Test d'ambiguïté

On peut tester si un automate fini non déterministe à m transitions est inambigu en temps $O(m^{3})$. On peut même calculer le degré d’ambiguïté, et savoir si l'ambiguïté est bornée, si elle croit polynomialement ou exponentiellement avec la longueur des mots.

Inclusion

Le problème d'inclusion consiste à tester si le langage reconnu par un automate $A$ est contenu dans le langage reconnu par un automate $B$. Le problème est bien entendu décidable. La question est celle de sa complexité.

Le problème de l'inclusion pour les automates inambigus est décidable en temps polynomial : il est dans la classe PTIME alors que ce même problème est PSPACE-complet pour les automates non déterministes. C'est d'ailleurs ce problème, décrit par Meyer et Stockmeyer en 1972 qui est le premier problème de cette classe.

La démonstration de cette propriété utilise le fait que le produit cartésien de deux automates inambigus est également inambigu.

Esquisse de la preuve

Soient A et B deux automates, et L(A) et L(B) les langages acceptés. On a L(A)\subset L(B) si et seulement si L(A\cap B)=L(A), où A\times B désigne l'automate produit reconnaissant L(A)\cap L(B). Les deux ensembles L(A\times B) et L(A) sont égaux si et seulement si le nombre de mots de longueur n dans L(A\times B) et égal au nombre de mots de longueur n dans L(A) pour tout n. Comme ces suites de nombres de mots satisfont une relation de récurrence linéaire, il suffit de vérifier qu'elles sont égales sur leur premiers termes, en fait pour n jusqu'au produit du nombre d'états de A et de B. Le nombre de mots de longueur n acceptés par un automate peut être calculé sur l'image commutative.

 

Universalité et équivalence

Le problème de l'universalité, c'est-à-dire de savoir si un automate accepte tous les mots, et le problème de l'équivalence, c'est-à-dire de savoir si deux automates acceptent les même mots, sont tous deux dans la classe PTIME, par réduction au problème de l'inclusion.

Extensions

Le coût en place de la transformation d'un automate inambigu en un automate déterministe est difficile à borner. Pour des alphabets unaires, une minoration est donnée par Okhotin à l'aide d'une fonction arithmétique liée à la fonction de Landau.

La notion d’ambiguïté s'étend aux transducteurs finis : un transducteur est fonctionnel si la transformation qu'il réalise est une fonction (partielle), il est inambigu si, pour tout mot, il existe un seul calcul de la valeur de la fonction. Il est décidable si la transduction réalisée par un transducteur est une fonction.

Il y a aussi une interprétation algébrique naturelle du degré d’ambiguïté au moyen d'automates pondérés : on associe à chaque transition le poids 1 dans le monoïde des entiers naturels ; le poids associé à un mot est alors la simplement le nombre de chemins acceptant ce mot.

Enfin, il existe la même notion pour les mots infinis et les automates les reconnaissants comme les automates de Büchi. Dans ce cas, il y a différence entre automates non déterministes et automates déterministes, puisque ces derniers reconnaissent moins de langages. Les automates de Büchi inambigus reconnaissent les mêmes langages que les automates de Büchi non déterministes.

L'ambiguïté d'un automate fini est simplement relié à la notion d'ambiguïté dans les grammaires formelles par la biais de la correspondance entre les automates et les grammaires régulières : chaque dérivation dans une grammaire régulière correspond à un calcul dans l'automate correspondant. C'est d'ailleurs la notion de grammaire qui est mise en avant dans l'article historique de Stearns et Hunt

Complexité des opérations

La complexité inambigüe d’un langage, notée usc(L) (pour « unambiguous state complexité ») est par définition le nombre minimal d’états d’un automate inambigu reconnaissant le langage L.

Soient L, M des langages rationnels sur un alphabet commun, avec usc(L)=m et usc(M)=n. On a les résultats suivants :

• image miroir : ${\text{usc}}(L^{\sim })={\text{usc}}(L)$, où $L^{\sim }$ est le langage miroir ;
• intersection : ${\text{usc}}(L\cap M)\leq mn$, et la borne est atteinte sur un alphabet à au moins 2 lettres.
• quotient gauche : ${\text{usc}}(L^{-1}M)\leq 2^{n}-1$, , et la borne est atteinte sur un alphabet à au moins 2 lettres.
• quotient droit : ${\text{usc}}(LM^{-1})\leq 2^{n}-1$, , et la borne est atteinte sur un alphabet à au moins 2 lettres.
• mélange :${\text{usc}}(L{\text{ш}}M)\leq 2^{nm}-1$, et la borne est atteinte sur un alphabet à au moins 5 lettres.
• produit : ${\text{usc}}(LM)\leq 3/42^{n+m}-1$, pourvu que $n,m\geq 2$, et la borne est atteinte sur un alphabet à au moins 6 lettres.
• étoile propre (opération plus)  : ${\text{usc}}(L)\leq 3/42^{m}-1$, pourvu que $m\geq 2$, et la borne est atteinte sur un alphabet à au moins 3 lettres.
• étoile : ${\text{usc}}(L)\leq 3/42^{m}$, pourvu que $m\geq 2$, et la borne est atteinte sur un alphabet à au moins 3 lettres.

Il est intéressant de comparer la complexité des opérations sur les langages au moyen d' automates déterministes, d'automates inambigus et [automate fini non déterministe | automates non déterministes]]. Pour cela, on introduit les notations :

• sc(L), nombre minimal d’états d’un automate déterministe reconnaissant le langage L.
• usc(L), comme ci-dessus le nombre minimal d’états d’un automate inambigu reconnaissant le langage L.
• nsc(L), nombre minimal d’états d’un automate non déterministe déterministe reconnaissant le langage L.

Dans la table suivante, les complexités sont résumées pour des langages donnés de complexité inambiguë n et m :

Opération	sc	nsc	usc
miroir	$2^{n}$	$n+1$	$n$
intersection	$mn$	$mn$	$mn$
quotient gauche	$2^{n}-1$	$n+1$	$2^{n}-1$
quotient droit	$n$	$n$	$2^{n}-1$
étoile positive	$3/4\cdot 2^{n}-1$	$n$	$3/4\cdot 2^{n}-1$
étoile	$3/4\cdot 2^{n}$	$n+1$	$3/4\cdot 2^{n}$
mélange	$\geq 2^{(m-1)(n-1)}$	$mn$	$2^{mn}$
produit	$m\cdot 2^{n}$	$m+n$	$3/4\cdot 2^{m+n}-1$
complément	$n$	$2^{n}$	$\leq 2^{0,79n+\log n}$ $\geq n^{2-\varepsilon }$

Bibliographie

• [Löding] Christof Löding, « Unambiguous Finite Automata », Developments in Language Theory,‎ 2013, p. 29–30 (lire en ligne) — Les transparents de sa présentation.
• [Isaak et Löding] Dimitri Isaak et Christof Löding, « Efficient inclusion testing for simple classes of unambiguous \u03c9-automata », Information Processing Letters, vol. 112, n^os 14-15,‎ août 2012, p. 578-582 (DOI 10.1016/j.ipl.2012.04.010, lire en ligne).
• [Meyer et Stockmeyer] Albert R. Meyer et Larry J. Stockmeyer, « The equivalence problem for regular expressions with squaring requires exponential space », 13th Annual Symposium on Switching and Automata Theory (SWAT 1972), Institute of Electrical & Electronics Engineers (IEEE),‎ octobre 1972, p. 125-129 (DOI 10.1109/swat.1972.29).
• [Arnold] André Arnold, « Rational ω-languages are non-ambiguous », Theoretical Computer Science, vol. 26, n^os 1-2,‎ septembre 1983, p. 221-223 (DOI 10.1016/0304-3975(83)90086-5).
• [Okhotin] Alexander Okhotin, « Unambiguous finite automata over a unary alphabet », Information and Computation, vol. 212,‎ mars 2012, p. 15-36 (DOI 10.1016/j.ic.2012.01.003, lire en ligne).
• [Stearns et Hunt] Richard E. Stearns et Harry B. Hunt, « On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata », 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), Institute of Electrical & Electronics Engineers (IEEE),‎ octobre 1981, p. 74–81 (DOI 10.1109/sfcs.1981.29).
• [Allauzen et. al.] Cyril Allauzen, Mehryar Mohri et Ashish Rastogi, « General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers », International Journal of Foundations of Computer Science, vol. 22, n^o 04,‎ 2011, p. 883–904 (DOI 10.1142/S0129054111008477, arXiv 0802.3254)
• [Colcombet] Thomas Colcombet, « Unambiguity in Automata Theory », Descriptional Complexity of Formal Systems,‎ 2015, p. 3–18 (DOI 10.1007/978-3-319-19225-3_1, lire en ligne)
• [Jirásek et. al.] Jozef Jirásek, Galina Jirásková et Juraj Šebej, « Operations on unambiguous automata », Developments in Language Theory,‎ 2016, p. 243–255 (DOI 10.1007/978-3-662-53132-7_20, lire en ligne).

Articles connexes

• Transducteur fini
• Automate pondéré
• Grammaire formelle
• Complexité en espace