Chapitre 3 Opérations sur les automates

Dans ce chapitre, nous voyons des opérations (algorithmiques) qui permettent à partir d’un ou plusieurs automates reconnaissant des langages L1 (éventuellement L2 aussi) de construire un nouvel automate A reconnaissant un langage L construit par opérations ensemblistes sur L1 et L2.

On commence tout d’abord par construire un automate complet qui reconnaît le même langage qu’un automate déterministe non complet.

3.1 Complétion d’un automate déterministe

Définition 3.1 (équivalence de deux automates) On dit que deux automates A et A sont équivalents s’ils reconnaissent le même langage, c’est-à-dire L(A)=L(A).

Proposition 3.1 Pour tout automate déterministe, il existe un automate déterministe complet équivalent.

Preuve. Soit A=(Q,i,A,δ,F) un automate déterministe. On définit un nouvel état p comme “puit” et qui n’appartient pas à Q, on définit A=(Q,i,A,δ,F) un nouvel automate où Q=Q{p} et δ(q,a)=δ(q,a) si δ(q,a) est déjà défini sinon on pose δ(q,a)=p et δ(p,a)=p pour tout aA.

L’automate A est bien un automate déterministe complet car la fonction δ est bien définie sur tout Q×A.

Il reste à voir que les deux automates reconnaissent bien le même langage.

Soit m=a1a2an un mot sur A. Supposons que m soit reconnu par A. Cela signifie qu’il existe une suite d’états q0,q1,,qnQ tels que q0=i est l’état initial qi+1=δ(qi,ai+1) pour tout 0i<n et qnF. On a donc aussi q0,q1,,qnQ tels que q0=i est l’état initial qi+1=δ(qi,ai+1) pour tout 0i<n et qnF. Donc m est bien reconnu par A.

Réciproquement si m est reconnu par A alors l’éxécution de l’automate correspondante ne passe pas par p le puit, sinon l’éxécution aboutirait au puit mais le puit n’est pas un état final. Ainsi, il existe une suite d’états q0,q1,,qnQ{p} tels que q0=i est l’état initial qi+1=δ(qi,ai+1) pour tout 0i<n et qnF. Comme tous les qi sont distincts de p, on a alors qi+1=δ(qi,ai+1) pour tout 0i<n et qnF. Ainsi, m est reconnu par A.

En conclusion L(A)=L(A).

Exemple 3.1

Un graphe déterministe non complet qui reconnait les mots commençant par 111.

Figure 3.1: Un graphe déterministe non complet qui reconnait les mots commençant par 111.

Un graphe déterministe complet qui reconnait aussi les mots commençant par 111.

Figure 3.2: Un graphe déterministe complet qui reconnait aussi les mots commençant par 111.

Remarque. Si on applique cette complétion à un automate qui était déjà complet, on va simplement ajouter un état p qui ne sera relié à aucun autre.

3.2 Émondage

Émonder verbe transitif (bas latin emundare, nettoyer, purifier). Soumettre un arbre à l’émondage. Synonymes : ébrancher - élaguer - tailler

Un automate peut posséder des états non accessibles ou non coaccessibles. Ces états sont inutiles pour la reconnaissance des mots, on peut donc les retirer et obtenir un automate émondé qui reconnaît le même langage. Littéralement, on retire les branches mortes.

Proposition 3.2 Pour tout automate déterministe il existe un automate émondé équivalent.

Preuve. Soit A=(Q,i,A,δ,F) un automate déterministe. Si i n’est pas coaccessible alors L(A)=. Dans ce cas, il suffit de prendre pour A l’automate émondé suivant :

Sinon comme i est toujours accessible, il y a au moins un état accessible et coaccessible. On définit alors A=(Q,i,A,δ,F)

  • Q est l’ensemble des états accessibles et coaccessible,
  • δ est la restriction de δ à Q×A,
  • F=QF.

Tous les états de A sont accessibles et coaccessibles car ils l’étaient déjà dans A. Ainsi A est émondé. Un mot est reconnu par A si et seulement si une éxécution aboutit à un sommet final et passe donc seulement par des états accessibles et coaccessibles. Un tel mot est reconnu par A si et seulement s’il est reconnu par A.

Remarque. Si on émonde un automate complet, l’automate obtenu n’est plus nécessairement complet. Par exemple, si on a complété un automate non complet, on a rajouté un puit qui est un état jamais coaccessible. Lors de l’émondage, cet état est retiré.

3.3 Reconnaissance du langage complémentaire

Rappelons que si L est un langage sur un alphabet A, le langage complémentaire Lc est l’ensemble des mots sur A qui ne sont pas dans L.

Proposition 3.3 Si A est un automate déterministe qui reconnaît un langage L alors il existe un automate A qui reconnait le langage complémentaire Lc.

Preuve. On commence par remplacer A par un automate A1=(Q,i,A,δ,F) complet qui reconnaît le même langage grâce à la Proposition 3.1.

Comme A1 est complet, pout tout m=a1an, il existe une exécution de l’automate avec des états q0,,qnq0=i et qj+1=δ(qj,aj+1) pour j<n. Le mot m est reconnu si et seulement qnF. Ainsi, avec l’automate A=(Q,i,A,δ,QF), le mot m est reconnu par A si et seulement s’il n’est pas reconnu par A1, c’est-à-dire mL(A). Au final, L(A)=L(A)c.

Remarque. Dans la preuve, il est important de commencer par compléter l’automate sinon les mots qui ne donnent pas d’éxécution de l’automate ne seront reconnus ni par A ni par A.

Un graphe déterministe complet qui reconnait aussi les mots qui ne commençent pas par 111.

Figure 3.3: Un graphe déterministe complet qui reconnait aussi les mots qui ne commençent pas par 111.

3.4 Reconnaissance de l’intersection de deux langages

Définition 3.2 (automate produit) Soit A1=(Q1,i1,A,δ1,F1) et A2=(Q2,i2,A,δ2,F2) deux automates sur le même alphabet A.

L’ automate produit A1×A2 est l’automate A=(Q,i,A,δ,F)

  • Q=Q1×Q2,
  • i=(i1,i2),
  • δ((q1,q2),a)=(δ1(q1,a),δ2(q2,a)) si δ1(q1,a),δ2(q2,a) sont bien définis,
  • F=F1×F2.

Proposition 3.4 Soit L1 et L2 deux langages sur un même alphabet A reconnus par des automates déterministes A1 et A2. L’automate produit A1×A2 reconnait l’intersection L1L2.

Preuve. Un mot m=a1an appartient à L1L2 si et seulement s’il existe deux suites d’états q10,,q1nQ1 et q20,,q2nQ2 telles que δk(qkj,aj+1)=qj+1, et qknFk pour tout j<n, k=1,2.

Si A=A1×A2 comme dans la Définition 3.2, alors on a exactement que m est accepté par A si et seulement si δ((q1j,q2j),aj+1)=(q1j+1,q2j+1) et (q1j+1,q2j+1)F=F1×F2, c’est-à-dire si et seulement si m est accepté par A1 et A2.

Ainsi, L(A1×A2)=L(A1)L(A2).

On obtient immédiatement la stabilité de la classe des langages reconnaissables par intersection finie.

Corollaire 3.1 Si L1 et L2 sont deux langages reconnaissables alors L1L2 l’est aussi.

3.5 Reconnaissance de l’union de deux langages

On a aussi stabilité de la classe des langages reconnaissables par union finie.

Proposition 3.5 Soit L1 et L2 deux langages reconnaissables alors L1L2 est aussi un langage reconnaissable.

Preuve. On utilise la propriété ensembliste suivante : pour deux sous-ensembles E,F d’un même ensemble, (FE)c=FcEc.

Ainsi pour deux langages L1,L2, L1L2=(Lc1Lc2)c. Donc si L1 et L2 sont reconnaissables alors Lc1 et Lc2 sont reconnaissables par la Proposition 3.3. Ainsi Lc1Lc2 est reconnaissable par la Proposition 3.4 et en conclusion L1L2=(Lc1Lc2)c est reconnaissable par la Proposition 3.3 de nouveau.

3.6 Exercices

Exercice 3.1 Écrire en pseudo-code un algorithme qui prend en entrée un automate déterministe et retourne en sortie un automate déterministe complet qui reconnait le même langage.

Exercice 3.2 Soit L un langage sur un alphabet A. On définit le langage des préfixes de L de la manière suivante :

Pre(L)={mA, mL,m

  1. Montrer que si L est un langage reconnaissable alors \operatorname{Pre}(L) aussi.
  2. Peut-on faire la même chose pour les suffixes ?

Exercice 3.3 Reprendre les automates de l’Exercice 3.5 et pour chacun d’eux donner

  • L’automate complété (s’il n’est pas déjà complet)
  • L’automate reconnaissant le langage complémentaire

Exercice 3.4 On considère les deux automates A_1 et A_2 suivants

Automate $A_1$.

Figure 3.4: Automate A_1.

Automate $A_2$.

Figure 3.5: Automate A_2.

  1. Décrire les langages L_1 et L_2 reconnus par A_1 et A_2.
  2. Construire l’automate produit A_1\times A_2.
  3. Quel est le langage reconnu par A_1\times A_2 ?
  4. Construire un automate qui reconnait L_1\cup L_2.

Exercice 3.5 Soit L un langage reconnaissable sur un alphabet \mathcal{A}.

  1. Montrer que le langage L' constitué de mots de L de longueur paire est aussi reconnaissable.
  2. Soit a\in\mathcal{A}. Montrer que le langage L'' des mots de L qui ne contiennent pas a est aussi reconnaissable.

Exercice 3.6 Soit A_1 et A_2 deux automates complets. L’automate A_1\times A_2 est-il complet ?

Exercice 3.7 Donner un automate émondé qui reconnait le même langage que l’automate suivant.

Automate à émonder.

Figure 3.6: Automate à émonder.