DM : Automates pondérés

DM de Langages Formels 2 : Automates pondérés

Younesse Kaddar

I. Quelques exemples

1.

En posant :

$Q ≝ {q_{0}}$
$𝛴 ≝ {a, b}$
$S ≝ (ℕ, +, \times, 0, 1)$

𝜆 (q_{0}) = 𝛾 (q_{0}) ≝ 1

𝜇 (q_{0}, a, q_{0}) ≝ 2

𝜇 (q_{0}, b, q_{0}) ≝ 1

on vérifie de manière immédiate que :

$⟦ 𝒜 ⟧ (w) = 2^{| w |_{a}}$

2.

Soit $Math input error$ un automate séquentiel.

En s’inspirant de l’exemple vu en TD sur le demi-anneau $⟨ ℙ (𝛴^{*}), \cup, \cdot, \emptyset, {𝜀} ⟩$ , en posant :

$Q^{'} ≝ Q$
$𝛴^{'} ≝ 𝛴$
$S^{'} ≝ ⟨ ℙ (𝛴^{*}), \cup, \cdot, \emptyset, {𝜀} ⟩$

𝜆^{'} (q) ≝ {\begin{cases} {m (q)} si m (q) est défini \\ \emptyset sinon \end{cases}

𝛾^{'} (q) ≝ {\begin{cases} {𝛾 (q)} si 𝛾 (q) est défini \\ \emptyset sinon \end{cases}

𝜇 (q, a, q^{'}) ≝ {\begin{cases} {q ⊛ a} si q ⟶_{𝒜}^{a} q^{'} est une transition de A \\ \emptyset sinon \end{cases}

alors

⟦ A^{'} ⟧ (w) ≝ {\begin{cases} {⟦ A ⟧ (w)} si ⟦ A ⟧ (w) est défini \\ \emptyset sinon \end{cases}

⇓

Donc avec le demi-anneau $S^{'}$ , $⟦ A ‘ ⟧$ est une fonction totale qui est en bijection immédiate avec $⟦ A ⟧$ sur le domaine de définition de $⟦ A ⟧$ .

Mais on veut l’égalité : on va donc modifier le demi-anneau, tout en restant aussi proche que possible de l’exemple précédent.

On introduit deux nouveaux symboles $⊥$ et $⊤$ dénotant respectivement un élément neutre (absorbant pour la deuxième loi) et un élément absorbant pour la première loi, et on pose :

S^{'} ≝ ⟨ 𝛴^{*} \cup {⊥, ⊤}, +, \cdot, ⊥, 𝜀 ⟩

où

$+$ est définie, pour tous $w \neq w^{'} \in 𝛴^{*}$ , de la manière suivante :

$+ (↗)$	$w$	$w^{'}$	$⊥$	$⊤$
$w$	$w$	$⊤$	$w$	$⊤$
$w^{'}$	$⊤$	$w^{'}$	$w^{'}$	$⊤$
$⊥$	$w$	$w^{'}$	$⊥$	$⊤$
$⊤$	$⊤$	$⊤$	$⊤$	$⊤$

$\cdot$ est la concaténation des mots, prolongée par : $\forall w \in 𝛴^{*},$
- $w \cdot ⊥ = ⊥ \cdot w = ⊥$
- $w \cdot ⊤ = ⊤ \cdot w = ⊤$
- $⊥ \cdot ⊤ = ⊤ \cdot ⊥ = ⊥$

On vérifie que $S^{'}$ est bien un demi-anneau :

$(𝛴^{*} \cup {⊥, ⊤}, +, ⊥)$ est bien un monoïde commutatif
- $+$ est associative : pour tous $x, y, z \in 𝛴^{*} \cup {⊥, ⊤}$ :
  - Si $x = ⊤$ ou $y = ⊤$ ou $z = ⊤$ :
    $x + (y + z) = ⊤ = (x + y) + z$
  - Sinon si $x = ⊥$ :
    $x + (y + z) = y + z = (x + y) + z$
  - Sinon si $y = ⊥$ :
    $x + (y + z) = x + z = (x + y) + z$
  - Sinon si $z = ⊥$ :
    $x + (y + z) = x + y = (x + y) + z$
  - Sinon si $x = y = z$ :
    $x + (y + z) = x = (x + y) + z$
  - Sinon :
    $x + (y + z) = ⊤ = (x + y) + z$
- $+$ est commutative (le tableau est symétrique) et d’élément neutre $⊥$
$(𝛴^{*}, \cdot, 𝜀)$ est un monoïde :
- $\cdot$ est associative : pour tous $x, y, z \in 𝛴^{*} \cup {⊥, ⊤}$ :
  - Si $x = ⊥$ ou $y = ⊥$ ou $z = ⊥$ :
    $x \cdot (y \cdot z) = ⊥ = (x \cdot y) \cdot z$
  - Sinon si $x = ⊤$ ou $y = ⊤$ ou $z = ⊤$ :
    $x \cdot (y \cdot z) = ⊤ = (x \cdot y) \cdot z$
  - Sinon (associativité de la concaténation pour les mots) :
    $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
- $\cdot$ a pour élément neutre $𝜀$
$\cdot$ est distributive par rapport à $+$ : pour tous $x, y, z \in 𝛴^{*} \cup {⊥, ⊤}$ :
- Si $x = ⊥$ :
  $\begin{matrix} ⊥ \cdot (y + z) = ⊥ = ⊥ \cdot y + ⊥ \cdot z \\ (y + z) \cdot ⊥ = ⊥ = y \cdot ⊥ + z \cdot ⊥ \end{matrix}$
- Sinon si $y = z = ⊥$ :
  $\begin{matrix} x \cdot (y + z) = ⊥ = x \cdot y + x \cdot z \\ (y + z) \cdot x = ⊥ = y \cdot x + z \cdot x \end{matrix}$
- Sinon si $x = ⊤$ :
  $\begin{matrix} ⊤ \cdot (y + z) = ⊤ = ⊤ \cdot y + ⊤ \cdot z \\ (y + z) \cdot ⊤ = ⊤ = y \cdot ⊤ + z \cdot ⊤ \end{matrix}$
  car l’un des deux derniers termes (à droite) vaut $⊤$
- Sinon si $y = z$ ou $z = ⊥$ :
  $\begin{matrix} x \cdot (y + z) = x \cdot y = x \cdot y + x \cdot z \\ (y + z) \cdot x = y \cdot x = y \cdot x + z \cdot x \end{matrix}$
- Sinon si $y = ⊥$ :
  $\begin{matrix} x \cdot (y + z) = x \cdot z = x \cdot y + x \cdot z \\ (y + z) \cdot x = z \cdot x = y \cdot x + z \cdot x \end{matrix}$
- Sinon ( $x \in 𝛴^{*}, y, z \in 𝛴^{*} \cup {⊤}$ et $y \neq z$ ) :
  $\begin{matrix} x \cdot (y + z) = x \cdot ⊤ = ⊤ = x \cdot y + x \cdot z \\ (y + z) \cdot x = ⊤ \cdot x = ⊤ = y \cdot x + z \cdot x \end{matrix}$
$⊥$ est absorbant pour $\cdot$

Il s’ensuit qu’en posant :

$Q^{'} ≝ Q$
$𝛴^{'} ≝ 𝛴$
$S^{'} ≝ ⟨ 𝛴^{*} \cup {⊥, ⊤}, +, \cdot, ⊥, 𝜀 ⟩$

𝜆^{'} (q) ≝ {\begin{cases} m (q) si m (q) est défini \\ ⊥ sinon \end{cases}

𝛾^{'} (q) ≝ {\begin{cases} 𝛾 (q) si 𝛾 (q) est défini \\ ⊥ sinon \end{cases}

𝜇 (q, a, q^{'}) ≝ {\begin{cases} (q ⊛ a) si q ⟶_{𝒜}^{a} q^{'} est une transition de A \\ ⊥ sinon \end{cases}

alors

$⟦ A^{'} ⟧ (w) ≝ {\begin{cases} ⟦ A ⟧ (w) si ⟦ A ⟧ (w) est défini \\ ⊥ sinon \end{cases}$

(la démonstration est analogue à ce qu’on a vu en TD : on le vérifie de manière immédiate, puisque $⊥$ est absorbant, et qu’on n’a qu’un seul chemin au plus dans $A$ acceptant $w$ , par déterminisme de la fonction séquentielle)

⇓

3.

$A ≝ (𝛴, Q, 𝛿, I, F)$

⇓

En posant :

$Q^{'} ≝ Q$
$𝛴^{'} ≝ 𝛴$
$S^{'} ≝ ⟨ ℕ, +, \times, 0, 1 ⟩$

𝜆^{'} (q) ≝ {\begin{cases} 1 si q est initial \\ 0 sinon \end{cases}

𝛾^{'} (q) ≝ {\begin{cases} 1 si q est final \\ 0 sinon \end{cases}

𝜇 (q, a, q^{'}) ≝ {\begin{cases} 1 si q^{'} \in 𝛿 (q, a) \\ 0 sinon \end{cases}

alors

\begin{matrix} ⟦ A^{'} ⟧ (w) ≝ \sum_{\underset{\in I}{\underset{⏟}{q_{1}}} ⟶_{A}^{w_{1}} q_{2} ⟶ \dots ⟶_{A}^{w_{n}} \underset{\in F}{\underset{⏟}{q_{n + 1}}}} \underset{n + 1 fois}{\underset{⏟}{1 \times \dots \times 1}} \\ = | {C ≝ \underset{\in I}{\underset{⏟}{q_{1}}} ⟶_{A}^{w_{1}} q_{2} ⟶ \dots ⟶_{A}^{w_{n}} \underset{\in F}{\underset{⏟}{q_{n + 1}}} ∣ q_{i} \in Q} | \\ = | {C chemin acceptant étiqueté par w} | \\ = p_{A} (w) \end{matrix}

4.

On note $S$ le demi-anneau produit ${☥, ☠, ❓, ⦰}^{| V |}$ (non commutatif) muni des lois :

$\times (↗)$	$☥$	$☠$	$❓$	$⦰$
$☥$	$☥$	$☥$	$☥$	$⦰$
$☠$	$☠$	$☠$	$☠$	$⦰$
$❓$	$☥$	$☠$	$❓$	$⦰$
$⦰$	$⦰$	$⦰$	$⦰$	$⦰$

$+ (↗)$	$☥$	$☠$	$❓$	$⦰$
$☥$	$☥$	$☥$	$☥$	$☥$
$☠$	$☥$	$☠$	$☠$	$☠$
$❓$	$☥$	$☠$	$❓$	$❓$
$⦰$	$☥$	$☠$	$❓$	$⦰$

définies composante par composante, où :

$☥$ sera interprété comme “la variable est vivante”
$☠$ sera interprété comme “la variable est morte”
$❓$ sera interprété comme “la variable est dans un état indéterminé”
$⦰$ est un élément neutre (pour $+$ ) absorbant rajouté artificiellement

NB : Par abus de notation, on notera de la même manière les lois définies sur ${☥, ☠, ❓, ⦰}$ et les lois produit correspondantes sur ${☥, ☠, ❓, ⦰}^{| V |}$

On vérifie bien que

$(S, +)$ est un monoïde commutatif d’élément neutre $⦰$
$(S, \times)$ est un monoïde d’élément neutre $❓$
$\times$ est distributive par rapport à $+$ :
- il suffit de le vérifier composante par composante : pour tous $x, y, z \in {☥, ☠, ❓, ⦰}$ :
  - Si $x = ⦰$ :
    $\begin{matrix} ⦰ \times (y + z) = ⦰ = ⦰ + ⦰ = ⦰ \times y + ⦰ \times z \\ (y + z) \times ⦰ = ⦰ = ⦰ + ⦰ = y \times ⦰ + z \times ⦰ \end{matrix}$
  - Sinon si $x = ❓$ :
    $\begin{matrix} ❓ \times (y + z) = y + z = ❓ \times y + ❓ \times z \\ (y + z) \times ❓ = y + z = y \times ❓ + z \times ❓ \end{matrix}$
  - Sinon si $y = z = ⦰$ :
    $\begin{matrix} x \times (y + z) = ⦰ = x \times y + x \times z \\ (y + z) \times x = ⦰ = y \times x + z \times x \end{matrix}$
  - Sinon :
    $\begin{matrix} x \times (y + z) = x = x \times y + x \times z \\ (y + z) \times x = y + z = y \times x + z \times x \end{matrix}$
$⦰$ est absorbant
$S$ est borné idempotent :
- $+$ est idempotent
- Comme $⦰ ⊑ ❓ ⊑ ☠ ⊑ ☥$ , $S$ ne contient aucune chaîne infinie décroissante non stationnaire.

Donc $S$ est un demi-anneau borné idempotent.

On pose $G^{'} ≝ (Q, 𝛴, S, 𝜆, 𝜇, 𝛾)$ , où

L’ensemble des états $Q$ est l’ensemble des sommets de $G$
$𝛴 ≝ I (V)$
$S ≝ ({☥, ☠, ❓, ⦰}^{| V |}, +, \times, ⦰, ❓)$

Dans la suite, on notera $x_{1}, \dots, x_{n}$ les variables de $V$ , et on indicera les vecteurs par $i$ pour dénoter leur coordonnée selon $x_{i}$ .

Pour tous $e \in I (V), q, q^{'} \in Q, i \in ⟦ 1, n ⟧$ :

𝜆 (q) ≝ (❓, \dots, ❓)

𝛾 (q) ≝ {\begin{cases} (☠, \dots, ☠) si q = q_{f} \\ (❓, \dots, ❓) sinon \end{cases}

𝜇 (q, e, q^{'})_{i} ≝ {\begin{cases} ☥ & si q ⟶^{e} q^{'} est une arête de G \\ et e est de la forme \\ if e’(V’) ou y := e’(V’) avec y \in V, x_{i} \in V^{'} \\ ☠ & sinon si q ⟶^{e} q^{'} est une arête de G \\ et e est de la forme \\ x_{i} := e’(V’) avec V^{'} \subseteq V \\ ❓ sinon \end{cases}

Pour tout chemin
$C ≝ q_{j_{1}} ⟶^{e_{j_{1}}} q_{j_{2}} ⟶^{e_{j_{2}}} \dots ⟶^{e_{j_{m - 1}}} q_{j_{m}} ≝ q_{f}$
montrons que la projection sur la $i$ -ème composante de $‖ C ‖$ permet de déterminer l’état de la variable $x_{i}$

Cas 1 : Si pour tout $k \in ⟦ 1, m - 1 ⟧$ , $x_{i}$ n’apparaît pas dans $e_{j_{k}}$ :

alors $x_{i}$ est morte dans $C$ , et :
$\begin{aligned} ‖ C ‖ & = 𝜆 (q_{j_{1}}) \prod_{k = 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) 𝛾 (q_{f}) \\ = (❓, \dots, ❓) (\prod_{k = 1}^{m - 1} (❓, \dots, ❓)) (☠, \dots, ☠) \\ = (☠, \dots, ☠) \end{aligned}$
donc on a bien $‖ C ‖_{i} = ☠$
Cas 2 : Sinon, on note $l$ le plus entier de $⟦ 1, m - 1 ⟧$ tel que $x_{i}$ apparaît dans $e_{j_{l}}$ : autrement dit, $e_{j_{l}}$ est la première instruction du chemin $C$ où apparaît $x_{i}$
- Sous-Cas 1 : si $e_{j_{l}}$ est de la forme $if e’(V’)$ ou $y := e’(V’)$ , avec $y \in V, x_{i} \in V^{'}$ : alors $x_{i}$ est vivante dans $C$ , et :
  $\begin{aligned} ‖ C ‖_{i} & = [𝜆 (q_{j_{1}}) \prod_{k = 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) 𝛾 (q_{f})]_{i} \\ = [((❓, \dots, ❓) \prod_{k = 1}^{l - 1} \underset{= (❓, \dots, ❓)}{\underset{⏟}{𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}})}}) 𝜇 (q_{j_{l}}, e_{j_{l}}, q_{j_{l + 1}}) \prod_{k = l + 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) (☠, \dots, ☠)]_{i} & (associativité) \\ = \overset{= ❓}{\overset{⏞}{[((❓, \dots, ❓) \prod_{k = 1}^{l - 1} (❓, \dots, ❓))]_{i}}} \underset{= ☥}{\underset{⏟}{[𝜇 (q_{j_{l}}, e_{j_{l}}, q_{j_{l + 1}})]_{i}}} [\prod_{k = l + 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) (☠, \dots, ☠)]_{i} \\ = \underset{= ☥}{\underset{⏟}{[𝜇 (q_{j_{l}}, e_{j_{l}}, q_{j_{l + 1}})]_{i}}} \underset{\neq ⦰}{\underset{⏟}{[\prod_{k = l + 1}^{m - 1} \underset{\neq ⦰}{\underset{⏟}{𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}})}} (☠, \dots, ☠)]_{i}}} \\ = ☥ \end{aligned}$
- Sous-Cas 2 : si $e_{j_{l}}$ est de la forme $x_{i} := e’(V’)$ , avec $V^{'} \subseteq V$ : alors $x_{i}$ est morte dans $C$ , et :
  $\begin{aligned} ‖ C ‖_{i} & = [𝜆 (q_{j_{1}}) \prod_{k = 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) 𝛾 (q_{f})]_{i} \\ = \overset{= ❓}{\overset{⏞}{[((❓, \dots, ❓) \prod_{k = 1}^{l - 1} (❓, \dots, ❓))]_{i}}} \underset{= ☠}{\underset{⏟}{[𝜇 (q_{j_{l}}, e_{j_{l}}, q_{j_{l + 1}})]_{i}}} [\prod_{k = l + 1}^{m - 1} 𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}}) (☠, \dots, ☠)]_{i} \\ = ☠ \underset{\neq ⦰}{\underset{⏟}{[\prod_{k = l + 1}^{m - 1} \underset{\neq ⦰}{\underset{⏟}{𝜇 (q_{j_{k}}, e_{j_{k}}, q_{j_{k + 1}})}} (☠, \dots, ☠)]_{i}}} \\ = ☠ \end{aligned}$

Dans tous les cas, le résultat est acquis.

Pour tout sommet $q \in Q$ , montrons que la projection sur la $i$ -ème composante de
$‖ q ‖ ≝ \sum_{C chemin partant de q} ‖ C ‖$
permet de déterminer l’état de la variable $x_{i}$

Supposons qu’il existe un chemin $C$ de $q$ vers $q_{f}$ où $x_{i}$ est vivante.

Alors par commutativité de $+$ :

\begin{aligned} ‖ q ‖_{i} & = \underset{= ☥}{\underset{⏟}{‖ C ‖_{i}}} + \sum_{C^{'} \neq C chemin partant de q} ‖ C^{'} ‖_{i} \\ = ☥ \end{aligned}

et le résultat est acquis.

Réciproquement, s’il n’existe aucun chemin de $q$ vers $q_{f}$ où $x_{i}$ est vivante : alors on ne peut pas avoir $‖ q ‖_{i} = ☥$ puisque $+ ({☠, ❓, ⦰}^{2}) \subseteq {☠, ❓, ⦰}$ , donc une somme d’éléments différents de $☥$ est différente de $☥$ .

Il vient donc que, pour tout sommet $q$ et chemin $C$ , les variables vivantes de $‖ q ‖$ et de $‖ C ‖$ sont celles dont la coordonnée vaut $☥$ .

5.

En se basant pour les observations faites précédemment, il apparaît que pour toute variable $x_{i}$ et pour tout état $q$ :

$x_{i}$ est vivante dans $q$ si et seulement si il existe un chemin
$q ≝ q_{j_{1}} ⟶^{e_{j_{1}}} q_{j_{2}} ⟶^{e_{j_{2}}} \dots ⟶^{e_{j_{m - 1}}} q_{j_{m}} ≝ q_{f}$
tel qu’en notant $l$ le plus entier de $⟦ 1, m - 1 ⟧$ tel que $x_{i}$ apparaît dans $e_{j_{l}}$ (i.e. $e_{j_{l}}$ est la première instruction du chemin où apparaît $x_{i}$ ), $e_{j_{l}}$ est de la forme
$if e’(V’) ou y := e’(V’)$
avec $y \in V, x_{i} \in V^{'}$
$x_{i}$ est morte dans $q$ si et seulement si elle n’est pas vivante dans $q$ et
- il existe un chemin
  $q ≝ q_{j_{1}} ⟶^{e_{j_{1}}} q_{j_{2}} ⟶^{e_{j_{2}}} \dots ⟶^{e_{j_{m - 1}}} q_{j_{m}} ≝ q_{f}$
  tel que la première instruction du chemin où apparaît $x_{i}$ est de la forme
  $x_{i} := e’(V’)$
  avec $V^{'} \subseteq V$
ou
- $x_{i}$ n’apparaît dans aucun chemin de $q$ à $q_{f}$

Si on veut que $‖ q ‖_{i}$ indique l’état de la variable $x_{i}$ dans l’état $q$ , chaque transition $q ⟶_{G}^{e} q^{'}$ doit donc vérifier les propriétés suivantes :

$P_{☥} (q ⟶_{G}^{e} q^{'}, i)$ :

si $‖ q ‖_{i} \neq ☥$ et $e$ est de la forme
$if e’(V’) ou y := e’(V’)$
avec $y \in V, x_{i} \in V^{'}$ , alors
$‖ q ‖_{i} = ☥$

$P_{☠} (q ⟶_{G}^{e} q^{'}, i)$ :

si $‖ q ‖_{i} \neq ☥$ et $e$ est de la forme
$x_{i} := e’(V’)$
avec $V^{'} \subseteq V$ , alors
$‖ q ‖_{i} = ☠$

$P_{❓} (q ⟶_{G}^{e} q^{'}, i)$ :

si $‖ q ‖_{i} \neq ☥$ ou $‖ q^{'} ‖_{i} \neq ☥$ et $x_{i}$ n’apparaît pas dans $e$ , alors
$‖ q ‖_{i} = ‖ q^{'} ‖_{i}$

On vérifie aussi que ces conditions sont suffisantes, d’après les observations précédentes.

De fait, la correction de l’algorithme suivant s’ensuit :

Initialiser tous les ||q||_i à ☠

Pour chaque x_i:
  Tant qu'il existe un transition t ≝ (q1 ⟶^e q') qui ne vérifie pas P_❓(t,i) ou P_☥(t,i):
      mettre ||q||_i ou ||q'||_i à ☥ pour vérifier la condition

NB : comme, à chaque étape de l’algorithme, les $‖ q ‖_{i}$ valent soit $☠$ , soit $☥$ : les conditions $P_{☠} (q ⟶_{G}^{e} q^{'}, i)$ sont toujours vérifiées, donc il est inutile d’en faire mention dans la boucle interne.

Terminaison

L’algorithme termine clairement, car

toute transition $t ≝ q ⟶_{G}^{e} q^{'}$ telle que $‖ q ‖_{i} = ☥$ vérifie $P_{☥} (t, i)$
toute transition $t ≝ q ⟶_{G}^{e} q^{'}$ telle que $‖ q ‖_{i} = ‖ q ‖_{i} \in {☥, ☠}$ vérifie $P_{❓} (t, i)$

et chaque $‖ q ‖_{i}$ ne peut être modifié (pour se voir attribuer la valeur $☥$ ) qu’au plus une fois dans la boucle principale.

Complexité

Dans le pire des cas, il faudra modifier chacun des $‖ q ‖_{i}$ , pour tous $q, i$ : et à chaque modification, on cherche une transition qui transgresse une des trois propriétés (en temps $O (| 𝛿 | m)$ où $𝛿$ est l’ensemble des transitions et $m$ la taille maximale des instructions $e \in I (V)$ ) donc

la complexité de l’algorithme est en
$O (| V | | Q | | 𝛿 | m)$
où

$Q$ est l’ensemble des états

$𝛿$ est l’ensemble des transitions

$m$ est la taille maximale d’une instruction de $I (V)$

NB : en fait, on ne modifiera jamais les $‖ q_{f} ‖_{i}$ puisqu’il n’y a pas de transition sortante de $q_{f}$ , mais on ne cherche pas à être aussi précis.

Exemple :

x := 0
y := x+1
if x == 0:
  x := x+y
  goto line 2

I (V) = {x := e(∅), y := e’(x), if e”(x), if ¬ e”(x), x := e”’(x, y)}

On pose $x_{1} ≝ x, x_{2} ≝ y$

Initialisation :

$q$	$‖ q ‖$
$q_{0}$	$(☠, ☠)$
$q_{1}$	$(☠, ☠)$
$q_{2}$	$(☠, ☠)$
$q_{3}$	$(☠, ☠)$
$q_{f}$	$(☠, ☠)$

$x_{i} = x$ :

La transition $q_{2} ⟶^{if ¬ e’‘(x)} q_{f}$ ne vérifie pas la propriété $P_{☥}$ :

La transition $q_{3} ⟶^{x := e’’‘(x, y)} q_{2}$ ne vérifie pas la propriété $P_{☥}$ :

La transition $q_{1} ⟶^{y := e’(x)} q_{2}$ ne vérifie pas la propriété $P_{☥}$ :

$x_{i} = y$ :

La transition $q_{3} ⟶^{x := e’’‘(x, y)} q_{2}$ ne vérifie pas la propriété $P_{☥}$ :

La transition $q_{2} ⟶^{if e’‘(x)} q_{3}$ ne vérifie pas la propriété $P_{❓}$ :

Sortie :

$q$	$‖ q ‖$
$q_{0}$	$(☠, ☠)$
$q_{1}$	$(☥, ☠)$
$q_{2}$	$(☥, ☥)$
$q_{3}$	$(☥, ☥)$
$q_{f}$	$(☠, ☠)$

Propriétés de clôture

6.

Soient $f : 𝛴^{*} ⟶ S$ une fonction reconnue par un automate pondéré $A ≝ (Q, 𝛴, S, 𝜆, 𝜇, 𝛾)$ , et $h : S ⟶ S^{'}$ un morphisme.

Alors en posant :

A_{h} ≝ (Q, 𝛴, S, 𝜆^{'}, 𝜇^{'}, 𝛾^{'})

$𝜆^{'} ≝ h \circ 𝜆$
$𝛾^{'} ≝ h \circ 𝛾$
$𝜇^{'} ≝ h \circ 𝜇$

il vient immédiatement (avec la notation matricielle) que pour tout mot $w$ :

\begin{aligned} ⟦ A_{h} ⟧ (w) & = 𝜆^{'} 𝜇^{'} (w) 𝛾^{'} \\ = (h \circ 𝜆) (h \circ 𝜇) (w) (h \circ 𝛾) \\ = h \circ (𝜆 𝜇 (w) 𝛾) & puisque h respecte les lois de S \\ = h (⟦ A ⟧ (w)) \\ = h (f) (w) \end{aligned}

Donc

si $f$ est reconnaissable et si $h$ est un morphisme, $h (f)$ est reconnaissable.

5.

Soient $f : 𝛴^{*} ⟶ S$ et $g : 𝛴^{*} ⟶ S$ deux fonctions reconnues respectivement par des automates pondérés $A_{f}$ et $A_{g}$ .

Alors l’automate union $A_{f + g}$ obtenu en juxtaposant (en mettant “côte à côte”) les automates $A_{f}$ et $A_{g}$ reconnaît $f + g$ .

En effet, pour tout mot $w$ (avec la notation matricielle et des notations évidentes) :

\begin{aligned} (f + g) (w) & = f (w) + g (w) \\ = ⟦ A_{f} ⟧ (w) + ⟦ A_{g} ⟧ (w) \\ = 𝜆_{f} 𝜇_{f} (w) 𝛾_{f} + 𝜆_{g} 𝜇_{g} (w) 𝛾_{g} \end{aligned}

et d’après la sémantique des automates pondérés, $𝜆_{f} 𝜇_{f} (w) 𝛾_{f} + 𝜆_{g} 𝜇_{g} (w) 𝛾_{g}$ est le poids de $w$ dans l’automate union (la somme des sommes des poids de tous les chemins étiquetés par $w$ dans chacun des automates égale la somme des sommes des poids de tous les chemins étiquetés par $w$ dans l’automate union, par définition de l’automate union).

Donc

si $f$ et $g$ sont reconnaissables, $f + g$ l’est aussi.

6.

Soient $f : 𝛴^{*} ⟶ S$ et $g : 𝛴^{*} ⟶ S$ deux fonctions reconnues respectivement par des automates pondérés $A_{f}$ et $A_{g}$ , et $(S, +, \times)$ un demi-anneau commutatif.

Rappels sur le produit de Kronecker $\otimes$ :

Si $A \in 𝕸_{m, n} (S)$ et $B \in 𝕸_{p, q} (S)$ :

A \otimes B ≝ (\begin{matrix} a_{11} B & \dots & a_{1 n} B \\ ⋮ & ⋱ & ⋮ \\ a_{m 1} B & \dots & a_{m n} B \end{matrix}) = (\begin{matrix} a_{11} b_{11} & a_{11} b_{12} & \dots & a_{11} b_{1 q} & \dots & \dots & a_{1 n} b_{11} & a_{1 n} b_{12} & \dots & a_{1 n} b_{1 q} \\ a_{11} b_{21} & a_{11} b_{22} & \dots & a_{11} b_{2 q} & \dots & \dots & a_{1 n} b_{21} & a_{1 n} b_{22} & \dots & a_{1 n} b_{2 q} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{11} b_{p 1} & a_{11} b_{p 2} & \dots & a_{11} b_{p q} & \dots & \dots & a_{1 n} b_{p 1} & a_{1 n} b_{p 2} & \dots & a_{1 n} b_{p q} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ a_{m 1} b_{11} & a_{m 1} b_{12} & \dots & a_{m 1} b_{1 q} & \dots & \dots & a_{m n} b_{11} & a_{m n} b_{12} & \dots & a_{m n} b_{1 q} \\ a_{m 1} b_{21} & a_{m 1} b_{22} & \dots & a_{m 1} b_{2 q} & \dots & \dots & a_{m n} b_{21} & a_{m n} b_{22} & \dots & a_{m n} b_{2 q} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} b_{p 1} & a_{m 1} b_{p 2} & \dots & a_{m 1} b_{p q} & \dots & \dots & a_{m n} b_{p 1} & a_{m n} b_{p 2} & \dots & a_{m n} b_{p q} \end{matrix})

On a montré en prépa (il suffit de faire le calcul) que :

Propriété du produit mixte :

Si $A, B, C, D$ sont des matrices à coefficients dans un demi-anneau commutatif, sous réserve de compatibilité des tailles :
$(A \otimes B) (C \otimes D) = (A C) \otimes (B D)$

Montrons que $f \times g$ est reconnaissable.

On note $n$ (resp. $m$ ) le nombre d’états de $A_{f}$ (resp. $A_{g}$ ).

Avec la notation matricielle (et des notations évidentes), pour tout mot $w$ :

\begin{aligned} (f \times g) (w) & = \underset{\in S}{\underset{⏟}{f (w)}} \times \underset{\in S}{\underset{⏟}{g (w)}} \\ = \underset{\in S}{\underset{⏟}{f (w)}} \otimes \underset{\in S}{\underset{⏟}{g (w)}} & (les éléments de S sont vus \\ comme des matrices 1×1) \\ = (𝜆_{f} 𝜇_{f} (w) 𝛾_{f}) \otimes (𝜆_{g} 𝜇_{g} (w) 𝛾_{g}) \\ = (𝜆_{f} \otimes 𝜆_{g}) (𝜇_{f} (w) \otimes 𝜇_{g} (w)) (𝛾_{f} \otimes 𝛾_{g}) & (produit mixte, car S est commutatif) \\ = (\begin{array}{c} 𝜆_{f, 1} 𝜆_{g, 1} \\ ⋮ \\ 𝜆_{f, 1} 𝜆_{g, m} \\ ⋮ \\ 𝜆_{f, n} 𝜆_{g, 1} \\ ⋮ \\ 𝜆_{f, n} 𝜆_{g, m} \end{array}) (\begin{array}{c} 𝜇_{f, 11} (w) 𝜇_{g} (w) & \dots & 𝜇_{f, 1 n} (w) 𝜇_{g} (w) \\ ⋮ & ⋱ & ⋮ \\ 𝜇_{f, n 1} (w) 𝜇_{g} (w) & \dots & 𝜇_{f, n n} (w) 𝜇_{g} (w) \end{array}) (\begin{array}{c} 𝛾_{f, 1} 𝛾_{g, 1} \\ ⋮ \\ 𝛾_{f, 1} 𝛾_{g, m} \\ ⋮ \\ 𝛾_{f, n} 𝛾_{g, 1} \\ ⋮ \\ 𝛾_{f, n} 𝛾_{g, m} \end{array}) \\ = ⟦ A_{f \times g} ⟧ (w) \end{aligned}

en posant $A_{f \times g} ≝ (Q^{'}, 𝛴, S, 𝜆^{'}, 𝜇^{'}, 𝛾^{'})$

où

$Q^{'} ≝ Q_{f} \times Q_{g}$
$\forall q \in Q_{f}, q^{'} \in Q_{g}, 𝜆^{'} ((q, q^{'})) ≝ 𝜆_{f} (q) \times 𝜆_{g} (q^{'})$
$\forall q \in Q_{f}, q^{'} \in Q_{g}, 𝛾^{'} ((q, q^{'})) ≝ 𝛾_{f} (q) \times 𝛾_{g} (q^{'})$
$\forall a \in 𝛴, q_{1}, q_{2} \in Q_{f}, q_{1}^{'}, q_{2}^{'} \in Q_{g}, 𝜇^{'} ((q_{1}, q_{1}^{'}), a, (q_{2}, q_{2}^{'})) ≝ 𝜇_{f} (q_{1}, a, q_{2}) \times 𝜇_{g} (q_{1}^{'}, a, q_{2}^{'})$

Donc

si $f$ et $g$ sont reconnaissables et si $S$ est commutatif, $f \times g$ est reconnaissable.

8.

L’hypothèse de commutativité de $S$ est cruciale : le résultat précédent n’est pas vrai dans le cas général.

Contre-exemple

On se place sur le demi-anneau non commutatif $S ≝ ⟨ ℙ (𝛴^{*}), \cup, \cdot, \emptyset, {𝜀} ⟩$ et sur l’alphabet $𝛴 ≝ {a, b}$ .

La fonction $f$ définie sur tout mot $w \in 𝛴^{*}$ par

f (w) ≝ {w}

est clairement reconnaissable.

Mais ce n’est pas le cas de $f \times f ≝ w \mapsto {w} \cdot {w} = {w^{2}}$ .

Par l’absurde, si $A ≝ (Q, 𝛴, S, 𝜆, 𝜇, 𝛾)$ à $N ≝ | Q |$ états reconnaissait $f \times f$ : on obtiendrait une contradiction en imitant la démonstration du lemme de pompage pour les automates finis.

En effet : le chemin $q_{j_{1}} ⟶^{a} q_{j_{2}} ⟶^{a} \dots ⟶^{b} \underset{\in F}{\underset{⏟}{q_{j_{m}}}}$ étiqueté par $a^{N + 1} b$ (il est unique car $f^{2} (a^{N + 1} b)$ est un singleton) passerait nécessairement deux fois par le même état $q_{j_{k}} = q_{j_{k^{'}}}$ (disons que $k < k^{'}$ ) lors de la lecture des $N + 1$ premières lettres, et il existerait deux entiers $r \geq 1, l \geq 0$ tels que

$k + l + r = N + 1$
le même chemin où on a bouclé $n$ fois sur $q_{j_{k}} ⟶^{a} \dots ⟶^{a} q_{j_{k + r - 1}} ⟶^{a} q_{j_{k + r}} = q_{j_{k}}$ serait étiqueté par $a^{k} (a^{r})^{n} a^{l} b$

Or :

$f^{2} (a^{N + 1} b) = {a^{N + 1} b a^{N + 1} b}$
$f^{2} (a^{k} (a^{r})^{n} a^{l} b) = {a^{k} (a^{r})^{n} a^{l} b a^{k} (a^{r})^{n} a^{l} b} = {u v^{n} w}$
- où $u v w = a^{2 (N + 1)} b$

on obtient une contradiction pour $n$ assez grand :

soit à cause du nombre de $b$ si $v$ contient la lettre $b$
soit, si $v$ ne contient pas la lettre $b$ , en considérant les facteurs à gauche et à droite du $b$ central (qui doivent être égaux dans $a^{k} (a^{r})^{n} a^{l} b a^{k} (a^{r})^{n} a^{l} b$ , mais qui ne peuvent pas l’être dans $u v^{n} w$ si $v$ ne contient pas la lettre $b$ )

On a donc montré que :

Si $S$ n’est pas commutatif, et $f$ et $g$ sont reconnaissables, $f \times g$ n’est pas nécessairement reconnaissable.

Share on

Twitter Facebook Google+ LinkedIn

DM de Langages Formels 2 : Automates pondérés

I.

Quelques exemples

1.

2.

3.

4.

5.

Terminaison

Complexité

Propriétés de clôture

6.

5.

6.

Rappels sur le produit de Kronecker ⊗ :

8.

Contre-exemple

Share on

Leave a comment

Rappels sur le produit de Kronecker $\otimes$ :