Cours 2 : Automate minimal

Automate minimal

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

\(a \cdot q = q'\) si $𝛿(q,a) = q’$

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

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

  1. $𝜑(q_{0,1}) = q_{0,2}$
  2. $∀a∈𝛴, 𝜑(a \cdot q ) = a \cdot 𝜑(q)$
  3. $q∈F_1 ⟺ 𝜑(q)∈F_2$
Isomorphisme :

morphisme bijectif

Résiduel $w^{-1}L$ à gauche de $L$ par $w$ :
\[w^{-1}L ≝ \lbrace v∈𝛴^\ast \mid wv ∈ L\rbrace\]

NB :

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

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

\[a^{-1}\cdot L = L(𝒜_a)\]

où $𝒜_a ≝ ⟨Q, 𝛴, 𝛿, a\cdot q_0, F⟩$ et, en général :

\[w^{-1}\cdot L = L(𝒜_w)\]

où $𝒜_w ≝ ⟨Q, 𝛴, 𝛿, w\cdot q_0, F⟩$

Si $𝒜$ est un automate, on pose :

\[L_q(𝒜) ≝ \lbrace v∈𝛴^\ast \mid q⟶^v_𝒜 q_f∈F \rbrace\]

NB :

\[\bigcup\limits_{q∈I} L_q(𝒜) = L(𝒜)\]

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

\[∀w∈𝛴^\ast, w^{-1}\cdot L(𝒜) = L_{w \cdot q_0}(𝒜)\]

D’où :

\[\vert \lbrace w^{-1} \cdot L \mid w∈𝛴^\ast \rbrace \vert ≤ \vert Q \vert\]

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 ≝ ⟨Q_L, 𝛴, 𝛿_L, 𝜀^{-1}\cdot L, F⟩\]

où

\[Q_L ≝ \lbrace w^{-1} \cdot L \mid w∈𝛴^\ast \rbrace\] \[∀a∈𝛴, a(w^{-1}\cdot L) ≝ (wa)^{-1} \cdot L\] 
  digraph {
    rankdir=LR;
    w1[label="w^{-1} L"];
    w2[label="(wa)^{-1} L"];
    w1 -> w2[label="a"];  
  }
\[F_L ≝ \lbrace w^{-1} \cdot L \mid w∈L \rbrace = \lbrace w^{-1} \cdot L \mid 𝜀∈w^{-1} \cdot L \rbrace\]

Lemme : \(L(𝒜_L) = L\)

Preuve :

NB :

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

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

Preuve (laborieuse) : par double inclusion :

  • Si $w∈L$ :

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

  • Si $w∈L(𝒜_L)$ :

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

MIEUX :

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

Par induction sur $w$.

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

Ex :

  digraph {
    rankdir=LR;
    aL[label="a^+ L'"];
    aEtL[label="a^* L'", shape="doublecircle"];
    L[shape = "hexagon"]
    L -> aL[label="b"];
    L -> ∅[label="a"];
    aL -> ∅[label="b"];
    aL -> aEtL[label="a"];
    aEtL -> aL[label="b"];
    aEtL -> aEtL[label="a"];
  }

$L = (ba^+)^+$, $L’ = (ba^+)^\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. $𝜀∈L_q ⟺ q∈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 $≡$ une relation d’équivalence sur $Q$.

Automate quotient $𝒜_≡$ de $𝒜$ par $≡$ :
\[𝒜_≡ ≝ ⟨Q_≡, 𝛴_≡, 𝛿_≡, q_≡, F_≡⟩\]

où :

  • $𝛿_≡ ≝ \lbrace ([q]≡, a, [q’]≡) \mid (q, a, q’)∈𝛿\rbrace$
  • $F_≡ ≝ \lbrace [q]_≡ \mid q∈F\rbrace$

alors

\[L(𝒜) ⊆ L(𝒜_≡)\]

  • En effet : Soit $w∈L(𝒜)$ : $w = a_1 ⋯ a_n$

    \[I \ni q_0 ⟶^{a_1}_𝒜 q_1 ⟶^{a_2}_𝒜 ⋯ ⟶^{a_n}_𝒜 q_n ∈F\]

    on a donc :

    \[I_≡ \ni [q_0] ⟶^{a_1}_{𝒜_≡} [q_1] ⟶^{a_2}_𝒜 ⋯ ⟶^{a_n}_{𝒜_≡} [q_n] ∈F_≡\]

    et $w∈L(𝒜_≡)$

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

une rel. d’éq. tq :

  • $q \sim q’ ⟹ a\cdot q \sim a\cdot q’$
  • $q \sim q’ ⟹ (q∈F ⟺ q’∈F)$

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

Preuve :

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

Soit $w=a_1 ⋯ a_n ∈ L(𝒜/\sim)$.

\[I_\sim \ni [q_0] ⟶^{a_1} [q_1] ⟶^{a_2}_𝒜 ⋯ ⟶^{a_n} [q_n] ∈F_\sim\]

On montre que : $∀i ∈⟦1, n⟧$, il existe

$q’_i ∈ [q_i]$ tq

\[q_0 ⟶^{a_1 ⋯ a_n} q'_i\]

  • Pour $i=0$ : $q’_0 = q_0$ convient

  • Induction :

    \[[q_{i}] ⟶^{a_i} [q_{i+1}]\]

    et par HR :

    \[q_0 ⟶^{a_1 ⋯ a_i} q'_i \sim q_i\]

    donc

    \[a_i \cdot q'_i \sim a_i \cdot q_i \sim q_{i+1}\]

    donc \(q'_{i+1} ≝ a_i \cdot q'_i\) convient.

    Enfin : $q_n ∈ F$ ssi $q’_n∈F$

    et donc l’exécution $q’_0 ⟶^w q’_n$ est acceptante.

Congruence de Nérode :

$q ≡ q’$ ssi $L_q(𝒜) = L_{q’}(𝒜)$

NB :

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

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

Algorithme de Moore

On définit une famille \((≡_i)_{i∈ℕ}\) d’équivalences sur $𝒜$ dét. comp. :

  • $q ≡_0 q’$ ssi $(q∈F ⟺ q’∈F)$
  • $∀i, q ≡_{i+1} q’$ ssi $q ≡_i q’$ et $∀a∈𝛴, a \cdot q ≡_i a \cdot q’$

Lemme :

\(∃k; ∀i, ≡_k \, = \, ≡_{i+k}\) et $≡_k$ est la congruence de Nérode

  1. La décroissance de la suite est claire

  2. Si $≡i \, = \, ≡{i+1}$, alors \(∀j, ≡_i \, = \, ≡_{i+j}\)

Donc $∃k ≤ \vert Q \vert$;

\[∀j, ≡_k \, = \, ≡_{k+j}\]
  1. On note $\sim$ l’équivalence de Nérode : montrons que \(\sim ⊆ ≡_i ∀i\)

Si $L_q = L_{q’}$, alors :

  • pour $i=0$ : $q∈F ⟺ q’∈F$ donc le résultat s’ensuit.

  • pour $i>0$ : $\sim ⊆ ≡_i$ par HR, donc

    \[q ≡_i q'\]

    et

    \[a \cdot q \sim a \cdot q' ∀a\]

    implique

    \[aq ≡_i aq'\]

    donc

    \[\sim ⊆ ≡_{i+1}\]
  1. \[≡_i ⊆ \sim\]

Soit $q ≡_{k+\vert w \vert} q’$

et donc

\[w \cdot q ≡_k w \cdot q'\]

et donc

\(w ∈L_q\) implique $w \cdot q∈F$ implique $w \cdot q’∈F$ implique $w∈L_{q’}$

Ex :

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

Partitions :

  • $≡_0 = \lbrace 0 \rbrace \lbrace 1, ⋯, n-1 \rbrace$

  • $≡_1 = \lbrace 0 \rbrace \lbrace n-1 \rbrace \lbrace 1, ⋯, n-2 \rbrace$

  • $≡_2 = \lbrace 0 \rbrace \lbrace n-1 \rbrace \lbrace n-2 \rbrace \lbrace 1, ⋯, n-3 \rbrace$

  • $\sim = \lbrace 0 \rbrace \lbrace n-1 \rbrace \lbrace n-2 \rbrace ⋯ \lbrace 1 \rbrace$

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

$P_i$ déjà construite,

\[P_i = B_1, ⋯, B_k\]

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

\[bloc(q)≤max\]

tq $q ≡_i q’$ ssi $bloc(q) = bloc(q’)$

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

algo en $O(\vert Q \vert^2 \cdot \vert 𝛴 \vert)$

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.

Leave a comment