Automate minimal

Rappel : si $𝒜=⟨Q,𝛴,𝛿,q_0,F⟩$ est déterministe complet, alors chaque lettre $a\in 𝛴$ peut être vue comme une action sur $Q$ :

$a\cdot q=q^{\prime }$ si $𝛿(q,a)=q^{\prime }$

Morphisme d’automates ${𝒜}_i=⟨Q_i,{𝛴}_i,{𝛿}_i,q_{0,i},F_i⟩$ pour $i\in \{1,2\}$ :

$𝜑:Q_1⟶Q_2$ est morphisme de ${𝒜}_1$ à ${𝒜}_2$ si

1. $𝜑(q_{0,1})=q_{0,2}$
2. $\forall a\in 𝛴,𝜑(a\cdot q)=a\cdot 𝜑(q)$
3. $q\in F_1⟺𝜑(q)\in F_2$

Isomorphisme :

morphisme bijectif

Résiduel $w^{-1}L$ à gauche de $L$ par $w$ :

$$w^{-1}L\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{v\in {𝛴}^{\ast }\mid wv\in L\}$$

NB :

• ${𝜀}^{-1}L=L$
• $(ua{)}^{-1}\cdot L=a^{-1}(u^{-1}\cdot L)$
• $a\in 𝛴,u\in {𝛴}^{\ast }$

Si $𝒜$ est dét. comp. :

où ${𝒜}_a\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q,𝛴,𝛿,a\cdot q_0,F⟩$ et, en général :

où ${𝒜}_w\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q,𝛴,𝛿,w\cdot q_0,F⟩$

Si $𝒜$ est un automate, on pose :

NB :

LEMME : Si $𝒜$ est déterministe complet, alors

$$\forall w\in {𝛴}^{\ast },w^{-1}\cdot L(𝒜)=L_{w\cdot q_0}(𝒜)$$

D’où :

Corollaire : Si $L$ est régulier, alors l’ensemble des résiduels à gauche de $L$ est fini.

Automate ${𝒜}_L$ des résiduels de $L$ :

$${𝒜}_L\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q_L,𝛴,{𝛿}_L,{𝜀}^{-1}\cdot L,F⟩$$

où

Lemme : $L({𝒜}_L)=L$

Preuve :

NB :

• $\forall w\in {𝛴}^{\ast },L_{w^{-1}\cdot L}({𝒜}_L)=w^{-1}\cdot L$

• $L_{(wa{)}^{-1}\cdot L}$

Preuve (laborieuse) : par double inclusion :

• Si $w\in L$ :

  • si $w=𝜀$ : alors $w^{-1}L=L$ état initial de ${𝒜}_L$, donc $w\in L({𝒜}_L)$
  • sinon si $w=av$ : $v\in a^{-1}L$ donc $v\in L_{v^{-1}L}({𝒜}_L)$ (hypothèse d’induction), et donc $av\in L_{(av{)}^{-1}L}({𝒜}_L)$

• Si $w\in L({𝒜}_L)$ :

  • Si $w=𝜀$, $L$ état initial de ${𝒜}_L$ est final, donc $𝜀=w\in L$
  • sinon, si $w=av$ : $v\in L_{a\cdot (v^{-1}L)}({𝒜}_L)$ donc $v\in a^{-1}L$, et $av\in L$

MIEUX :

Lemme : $w(L)=w^{-1}L$

Par induction sur $w$.

• Si $w\in L$ alors $𝜀\in w^{-1}L$ et donc $w\in L({𝒜}_L)$
• Si $w\in L({𝒜}_L)$ alors $𝜀\in w^{-1}L$, et donc $w\in L$

Ex :

$L=(b{a}^{+}{)}^{+}$, $L^{\prime }=(b{a}^{+}{)}^{\ast }$

Lemme : Soit $𝒜$ dét. comp.

Alors $𝜑:q\mapsto L_q$ est un morphisme surjectif d’automates.

Preuve :

1. $L_{q_0}(𝒜)=L$
2. $L_{a\cdot q}=a^{-1}{L}_q=a(L_q)$
3. $𝜀\in L_q⟺q\in F$

Donc l’automate des résiduels est l’unique automate dét. comp. minimal à isomorphisme près.

NB : par contre, le problème de l’égalité entre deux langages réguliers (en l’occurrence, ici : les résiduels) est PSPACE-complet : l’algo n’est pas du tout efficace !

Algorithme de minimisation

Soit $\equiv$ une relation d’équivalence sur $Q$.

Automate quotient ${𝒜}_{\equiv }$ de $𝒜$ par $\equiv$ :

$${𝒜}_{\equiv }\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q_{\equiv },{𝛴}_{\equiv },{𝛿}_{\equiv },q_{\equiv },F_{\equiv }⟩$$

où :

• $𝛿_≡ ≝ \lbrace ([q]≡, a, [q’]≡) \mid (q, a, q’)∈𝛿\rbrace$
• $F_{\equiv }\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{[q{]}_{\equiv }\mid q\in F\}$

alors

• En effet : Soit $w\in L(𝒜)$ : $w=a_1\cdots a_n$

  $$I\ni q_0{⟶}_{𝒜}^{a_1}{q}_1{⟶}_{𝒜}^{a_2}\cdots {⟶}_{𝒜}^{a_n}{q}_n\in F$$

  on a donc :

  $$I_{\equiv }\ni [q_0]{⟶}_{{𝒜}_{\equiv }}^{a_1}[q_1]{⟶}_{𝒜}^{a_2}\cdots {⟶}_{{𝒜}_{\equiv }}^{a_n}[q_n]\in F_{\equiv }$$

  et $w\in L({𝒜}_{\equiv })$

Congruence $\sim$ sur $𝒜$ dét. comp. :

une rel. d’éq. tq :

• $q\sim q^{\prime }⟹a\cdot q\sim a\cdot q^{\prime }$
• $q\sim q^{\prime }⟹(q\in F⟺q^{\prime }\in F)$

Lemme : Si $\sim$ est une congruence, alors $L(𝒜)=L(𝒜/\sim )$

Preuve :

La seule chose à montrer est $L(𝒜/\sim )\subseteq L(𝒜)$

Soit $w=a_1\cdots a_n\in L(𝒜/\sim )$.

On montre que : $\forall i\in ⟦1,n⟧$, il existe

$q_i^{\prime }\in [q_i]$ tq

• Pour $i=0$ : $q_0^{\prime }=q_0$ convient

• Induction :

  $$[q_i]{⟶}^{a_i}[q_{i+1}]$$

  et par HR :

  $$q_0{⟶}^{a_1\cdots a_i}{q}_i^{\prime }\sim q_i$$

  donc

  $$a_i\cdot q_i^{\prime }\sim a_i\cdot q_i\sim q_{i+1}$$

  donc $q_{i+1}^{\prime }\stackrel{\scriptscriptstyle\mathrm{def}}{=}{a}_i\cdot q_i^{\prime }$ convient.

  Enfin : $q_n\in F$ ssi $q_n^{\prime }\in F$

  et donc l’exécution $q_0^{\prime }{⟶}^w{q}_n^{\prime }$ est acceptante.

Congruence de Nérode :

$q\equiv q^{\prime }$ ssi $L_q(𝒜)=L_{q^{\prime }}(𝒜)$

NB :

• on vérifie aisément que c’est une congruence

• $A/\equiv$ est isomorphe à l’automate minimal : $𝜑:q\mapsto L_q$ devient injective

Algorithme de Moore

On définit une famille $({\equiv }_i{)}_{i\in \mathbb{N}}$ d’équivalences sur $𝒜$ dét. comp. :

• $q{\equiv }_0{q}^{\prime }$ ssi $(q\in F⟺q^{\prime }\in F)$
• $\forall i,q{\equiv }_{i+1}{q}^{\prime }$ ssi $q{\equiv }_i{q}^{\prime }$ et $\forall a\in 𝛴,a\cdot q{\equiv }_{i}a\cdot q^{\prime }$

Lemme :

$\exists k;\forall i,{\equiv }_k={\equiv }_{i+k}$ et ${\equiv }_k$ est la congruence de Nérode

1. La décroissance de la suite est claire

2. Si $≡i \, = \, ≡{i+1}$, alors $\forall j,{\equiv }_i={\equiv }_{i+j}$

Donc $\exists k\le |Q|$;

1. On note $\sim$ l’équivalence de Nérode : montrons que $\sim \subseteq {\equiv }_i\forall i$

Si $L_q=L_{q^{\prime }}$, alors :

• pour $i=0$ : $q\in F⟺q^{\prime }\in F$ donc le résultat s’ensuit.

• pour $i>0$ : $\sim \subseteq {\equiv }_i$ par HR, donc

  $$q{\equiv }_i{q}^{\prime }$$

  et

  $$a\cdot q\sim a\cdot q^{\prime }\forall a$$

  implique

  $$aq{\equiv }_{i}a{q}^{\prime }$$

  donc

  $$\sim \subseteq {\equiv }_{i+1}$$

1. $${\equiv }_i\subseteq \sim$$

Soit $q{\equiv }_{k+|w|}{q}^{\prime }$

et donc

et donc

$w\in L_q$ implique $w\cdot q\in F$ implique $w\cdot q^{\prime }\in F$ implique $w\in L_{q^{\prime }}$

Ex :

${𝒜}_n$ “circulaire” avec $n$ états, d’état initial et final $0$

Partitions :

• ${\equiv }_0=\{0\}\{1,\cdots ,n-1\}$

• ${\equiv }_1=\{0\}\{n-1\}\{1,\cdots ,n-2\}$

• ${\equiv }_2=\{0\}\{n-1\}\{n-2\}\{1,\cdots ,n-3\}$

• $\sim =\{0\}\{n-1\}\{n-2\}\cdots \{1\}$

⟶ L’algorithme naïf en $O(|Q{|}^3\cdot |𝛴|)$

$P_i$ déjà construite,

Concrètement, on associe à chaque $q\in Q$ un entier

tq $q{\equiv }_i{q}^{\prime }$ ssi $bloc(q)=bloc(q^{\prime })$

Pour tout a∈𝛴:
  Pour tout q∈Q:
    bloc(q) = max × bloc(q) + bloc(a \cdot q)
  max = 2max +1

algo en $O(|Q{|}^2\cdot |𝛴|)$

NB :

• alogrithme d’Hopcroft en $O(n\log n)$

• union find : pas très bon ici

• En TD : un algorithme en $2^{O(n)}$ dit de “double renversement” de BROZOZWSKI

fonctionne sur un automate non dét. !

NB :

• mais en pratique : tous ces algos sont plutôt efficace (MOORE, BROZOZWSKI, HOPCROPFT)

• très souvent : BROZOZWSKI est même plus efficace que MOORE et HOPCROPFT ! (car les opérations de renversement sont très faciles à faire en pratique)

• En espérance : MOORE est en $𝛳(n\log n)$ : donc en moyenne, MOORE est aussi bon qu’HOPCROPFT.