TD 3 : Minimisation

Énoncé

EX 1

  digraph {
    1[shape="hexagon"];
    4[shape="doublecircle"];
    5[shape="doublecircle"];
    1 -> 2[label="a"];
    2 -> 3[label="a"];
    3 -> 2[label="b"];
    2 -> 7[label="b"];
    7 -> 7[label="a,b"];
    4 -> 5[label="a"];
    1 -> 4[label="b"];
    4 -> 7[label="b"];
    5 -> 7[label="a"];
    5 -> 6[label="b"];
    6 -> 6[label="b"];
    1 -> 2[label="a"];
    6 -> 5[label="a"];
  }

$≡_0 : 4 5 \mid 1 2 3 6 7$

$≡_1 : 4 \mid 5 \mid 1 \mid 2 3 7 \mid 6$

$≡_2 : 4 \mid 5 \mid 1 \mid 2 3 7 \mid 6$

  digraph {
    1[shape="hexagon"];
    4[shape="doublecircle"];
    5[shape="doublecircle"];
    237 -> 237[label="a,b"];
    3 -> 237[label="b"];
    4 -> 5[label="a"];
    1 -> 4[label="b"];
    4 -> 237[label="b"];
    5 -> 237[label="a"];
    5 -> 6[label="b"];
    6 -> 6[label="b"];
    1 -> 237[label="a"];
    6 -> 5[label="a"];
  }

  digraph {
    1[shape="hexagon"];
    2[shape="doublecircle"];
    3[shape="doublecircle"];
    1 -> 2[label="a"];
    1 -> 3[label="b"];
    2 -> 3[label="a"];
    3 -> 3[label="b"];
    3 -> 4[label="a"];
    4 -> 5[label="a"];
    5 -> 4[label="a"];
    4 -> 6[label="b"];
    6 -> 3[label="a"];
    6 -> 5[label="b"];
    5 -> 6[label="b"];
  }

$≡_0 : 2 3 \mid 1 4 5 6$

$≡_1 : 2 \mid 3 \mid 1 \mid 4 5 \mid 6$

$≡_2 : 2 \mid 3 \mid 1 \mid 4 5 \mid 6$

  digraph {
    1[shape="hexagon"];
    2[shape="doublecircle"];
    3[shape="doublecircle"];
    1 -> 2[label="a"];
    1 -> 3[label="b"];
    2 -> 3[label="a"];
    3 -> 3[label="b"];
    3 -> 45[label="a"];
    45 -> 45[label="a"];
    45 -> 6[label="b"];
    6 -> 3[label="a"];
    6 -> 45[label="b"];
  }

EX 2

$E = ((a(a+b)^2+b)^\ast a(a+b))^\ast$

Deux méthodes :

  1. NFA ⟶ Déterminisation ⟶ Moore
  2. Automate des résiduels

Automate des résiduels :

$a^{-1} L = (a+b)^2 L^+ + (a+b)L$

$b^{-1} L = L^+$

$a^{-1} a^{-1} L = (a+b) L^+ + L$

$b^{-1} a^{-1} L = a^{-1} a^{-1} L$

$a^{-1} b^{-1} L = a^{-1} L$

$b^{-1} b^{-1} L = b^{-1} L$

$a^{-1} a^{-1} a^{-1} L = L^+ + a^{-1} L$

$b^{-1} a^{-1} a^{-1} L = L^+ + b^{-1} L = b^{-1} L$

$a^{-1} a^{-1} a^{-1} a^{-1} L = (a+b)^2 L^+ + (a+b)L + L$

$b a^{-1} a^{-1} a^{-1} a^{-1} L = a^{-1} a^{-1} L$

$a^{-1} a^{-1} a^{-1} a^{-1} a^{-1} L = a^{-1} a^{-1} a^{-1} a^{-1} L$

  digraph {
    1[label="L",shape="hexagon"];
    2[label="a^{-1} L"];
    3[label="a^{-1} a^{-1} L", shape="doublecircle"];
    4[label="a^{-1} a^{-1} a^{-1} L"];
    5[label="a^{-1} a^{-1} a^{-1} a^{-1} L", shape="doublecircle"];
    6[label="b^{-1} L"];

    1 -> 2[label="a"];
    2 -> 3[label="a,b"];
    3 -> 4[label="a"];
    4 -> 3[label="b"];
    4 -> 5[label="a"];
    5 -> 5[label="a"];
    5 -> 3[label="b"];
    3 -> 6[label="b"];
    6 -> 2[label="a"];
    6 -> 6[label="b"];
    1 -> 6[label="b"];
  }

M2 :

  digraph {
    1[shape="doublecircle"];
    1 -> 2[label="a"];
    2 -> 1[label="a,b"];
    1 -> 4[label="a"];
    1 -> 3[label="b"];
    4 -> 5[label="a,b"];
    5 -> 6[label="a,b"];
    6 -> 3[label="b"];
    6 -> 2[label="a"];
    3 -> 3[label="b"];
    3 -> 2[label="a"];
    3 -> 4[label="a"];
  }

EX 3

Soit $𝒜$ le déterminisé d’un automate co-déterministe et co-accessible qui reconnaît $L$.

Montrons que $𝒜$ est isomorphe à l’automate minimal.

Montrons que pour tous états $q ≠ q’$ de $𝒜$ :

\[L_q ≠ L_{q'}\]

C’est le cas ssi il existe un mot $w$ qui prononcé depuis l’état initial de ${}^t 𝒜$ (qui est déterministe), arrive à $q$ mais n’arrive pas à $q’$.

Or, c’est le cas pour tous les mots, puisque ${}^t 𝒜$ est accessible et déterministe.


$𝒜 = ⟨𝛴, Q, I, \lbrace p_f \rbrace, 𝛿⟩$ co-acc, co-dét.

Soit $𝒜_d = ⟨𝛴, Q_d⊆ 2^Q, I, F, 𝛿⟩$ son déterminisé.

Montrons que pour tous $q, q’∈Q_d$,

\[L_q = L_q' ⟹ q = q'\]

Soient $q, q’$ tq $L_q = L_{q’}$, montrons que $q⊆q’$

(Par symétrie, on aura $q=q’$)

Soit $p∈q$. Comme $𝒜$ est co-acc, il existe $w∈𝛴^\ast$ tq

\[p⟶^w p_f\]

On a $w∈L_q=L_{q’}$, donc

\[q'⟶^w \underbrace{f∈F}_{\text{ i.e } p_f∈f}\]

Donc il existe $p’∈q’$ tq

\[p'⟶^w p_f\]

(car $q⟶^a \lbrace p’ \mid ∃p∈q; p⟶^a p’\rbrace$, et par extension : $q⟶^w \lbrace p’ \mid ∃p∈q; p⟶^w p’\rbrace$)

Donc dans $𝒜$ :

  • $p ⟶^w p_f$
  • $p’ ⟶^w p_f$

Comme $𝒜$ est co-déter.

\[p=p'\]

et $p∈q’$.


NB : ${}^t𝒜 = tr(𝒜)$ est l’automate où toutes les flèches de $𝒜$ ont été retournées.

L’algo calcule :

\[det(tr(det(tr(𝒜))))\]

(où $det(𝒜)$ est le déterminisé accessible)

Complexité : $O(2^n)$

car calculer $det(𝒜)$ se fait en $O(\min(2^{\vert 𝒜 \vert}), \vert det(A) \vert)$

EX 4

1.

L’automate produit des automates minimaux qui reconnaît $L∪K$ (les états finals sont les états dont une des composantes est un état final) a $Sc(L)Sc(K)$ états, donc :

\[Sc(L∪K) ≤ Sc(L)Sc(K)\]

Si $𝒜_L = ⟨𝛴, Q_L, i_L, F_L, 𝛿_L⟩$ et $𝒜_K = ⟨𝛴, Q_K, i_K, F_K, 𝛿_K⟩$ et

\(𝒜_{L∪K} = ⟨𝛴, Q_L×Q_K, (i_L, i_K), F_L×Q_K∪Q_L×F_K, 𝛿_{L∪K}⟩\) où

\[𝛿_{L∪K} ≝ \lbrace (q_1, q_2), a, (q'_1, q'_2) \mid (q_1, q_2)∈𝛿_L \text{ et } (q'_1, q'_2)∈𝛿_K \rbrace\]

2.

L’automate produit des automates minimaux qui reconnaît $L∩K$ (les états finals sont les états dont les deux composantes sont des états finals) a $Sc(L)Sc(K)$ états, donc :

\[Sc(L∩K) ≤ Sc(L)Sc(K)\]

3.

L’automate miroir du déterminisé accessible de l’automate minimal de $L$ reconnaît $L^t$ et a $2^{Sc(L)}$ états, donc :

\[Sc(L^t) ≤ 2^{Sc(L)}\]

4.

\[𝒜_{L.K} = ⟨𝛴, Q_L \sqcup Q_K, i_L, F_K ∪ 1_{𝜀∈K} F_L, 𝛿 ≝ 𝛿_L ∪ 𝛿_K ∪ \lbrace (f,a,q) \mid f∈F_L, (i_K, a, q)∈𝛿_K \rbrace⟩\]

$𝒜’{LK}$ le déterminisé accessible de $𝒜{LK}$

\[𝒜'_{LK} ≝ ⟨𝛴, Q', q_0, F, 𝛿⟩\]

Pour tout $q∈Q’$, $\vert q∩Q_L \vert = 1$.

Par réc sur $\vert w \vert$ tq

\[\lbrace i_L \rbrace ⟶^w q\]
  • Si $w=𝜀$, $q = \lbrace i_L \rbrace$ : OK

  • Si $\lbrace i_L \rbrace ⟶^w \lbrace q_L \rbrace ∪ \underbrace{P}_{⊆Q_K} ⟶^a P’$

Comme $𝒜_L$ est complet,

$∃q’_L; q_L ⟶^a q’_L$, donc $q’_L∈P’$

Réciproquement, si $q’‘_L ∈ P’∩Q_L$,

\[∃q∈ \lbrace q_L \rbrace ∪ P; q⟶^a q''_L\]

nécessairement $q∈Q_L$, donc $q=q_L$, et

\[q''_L = q'_L\]

Donc

\[Sc(LK)≤ \vert Sc(L) \vert \cdot 2^{\vert Q_K \vert}\]

? Pourquoi on a même

\[Sc(LK)≤ \vert Sc(L) \vert \cdot 2^{\vert Q_K \vert} - 2^{\vert Q_K \vert-1}\]

⟶ car :

pour tous $P⊆Q_K \backslash \lbrace i_k \rbrace, f∈F_L$,

\[L_{\lbrace f, i_K \rbrace ∪ P} = L_{\lbrace f \rbrace ∪ P}\]

car

\[\lbrace f, i_K \rbrace ∪ P ⟶^a P' \\ ⟺ \lbrace f \rbrace ∪ P ⟶^a P'\]

puisque

\[i_K ⟶^a q ⟹ f ⟶^a q\]

EX 5

1.

\[𝛿' ≝ \lbrace (q, \bigcup\limits_{q⟶^L q'}, q') \mid q≠q' \rbrace ∪ \lbrace (q, \lbrace 𝜀 \rbrace ∪ \bigcup\limits_{q⟶^L q}, q') \rbrace\]

2.

\[𝛿' = \lbrace (q_1, L_{q_1 q_2} + L_{q_1 q} L_{qq}^\ast L_{qq_2}, q_2) \mid q_1 ⟶^{L_{q_1q_2}}q_2, q_1 ⟶^{L_{q_1q}}q, q ⟶^{L_{qq}}q, q⟶^{L_{qq_2}}q_2 \rbrace \\ ∪ 𝛿 \backslash \lbrace \text{ transitions arrivant en ou partant de } q\rbrace\]

Leave a comment