TD 3 : Minimisation
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 :
- NFA ⟶ Déterminisation ⟶ Moore
- 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\]
Leave a comment