DM : Automates pondérés

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

Younesse Kaddar

I.

Quelques exemples

1.

  digraph {
    rankdir=LR;
    subgraph cluster_0{
      label = "𝒜"
      q_0;
      b1, b2[style=invis];
    }
    b1 -> q_0[label="1"];
    q_0 -> q_0[label="a / 2  |  b / 1"];
    q_0 -> b2[label="1"];
  }

En posant :

  • $Q ≝ \lbrace q_0 \rbrace$
  • $𝛴 ≝ \lbrace a,b \rbrace$
  • $S ≝ (ℕ, +, ×, 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^{\vert w \vert_a}\]

2.

Soit ${\cal A} ≝ (Q, A, B, q_0, \odot, ⊛, m, ρ)$ un automate séquentiel.

En s’inspirant de l’exemple vu en TD sur le demi-anneau $⟨ ℙ(𝛴^\ast), ∪, \cdot, ∅, \lbrace 𝜀 \rbrace ⟩$, en posant :

  • $Q’ ≝ Q$
  • $𝛴’ ≝ 𝛴$
  • $S’ ≝ ⟨ ℙ(𝛴^\ast), ∪, \cdot, ∅, \lbrace 𝜀 \rbrace ⟩$
\[𝜆'(q) ≝ \begin{cases} \lbrace m(q) \rbrace \text{ si } m(q) \text{ est défini} \\ ∅ \text{ sinon} \end{cases}\] \[𝛾'(q) ≝ \begin{cases} \lbrace 𝛾(q) \rbrace \text{ si } 𝛾(q) \text{ est défini} \\ ∅ \text{ sinon} \end{cases}\] \[𝜇(q, a, q') ≝ \begin{cases} \lbrace q ⊛ a\rbrace \text{ si } q ⟶^a_𝒜 q' \text{ est une transition de } {\cal A} \\ ∅ \text{ sinon} \end{cases}\]

alors

\[⟦{\cal A} '⟧(w) ≝ \begin{cases} \lbrace ⟦{\cal A}⟧(w) \rbrace \text{ si } ⟦{\cal A}⟧(w) \text{ est défini } \\ ∅ \text{ sinon} \end{cases}\] 
  digraph {
    rankdir=LR;
    subgraph cluster_0{
      label = "𝒜"
      q_0, q_1, q_2;
      b1, b2[style=invis];
    }
    b1 -> q_0[label="m(q_0)"];
    q_0 -> q_0[label="a / q_0 ⊛ a"];
    q_0 -> q_1[label="b / q_0 ⊛ b"];
    q_1 -> q_1[label="a / q_1 ⊛ a"]
    q_1 -> q_2[label="b / q_1 ⊛ b"];
    q_2 -> q_2[label="a, b / q_2 ⊛ a, q_2 ⊛ b"];
    q_2 -> b2[label="𝛾(q_2)"];
  }

⇓

  digraph {
    rankdir=LR;
    subgraph cluster_0{
      label = "𝒜'"
      q_0, q_1, q_2;
      b1, b2, b3[style=invis];
    }
    b1 -> q_0[label="{m(q_0)}"];
    q_0 -> q_0[label="a / {q_0 ⊛ a}"];
    q_0 -> q_1[label="b / {q_0 ⊛ b}"];
    q_1 -> q_1[label="a / {q_1 ⊛ a}"]
    q_1 -> q_2[label="b / {q_1 ⊛ b}"];
    q_2 -> q_2[label="a, b / {q_2 ⊛ a}, {q_2 ⊛ b}"];
    q_2 -> b2[label="{𝛾(q_2)}"];
    q_1 -> b3[label="∅"];
  }

Donc avec le demi-anneau $S’$, $⟦{\cal A} ‘⟧$ est une fonction totale qui est en bijection immédiate avec $⟦{\cal A}⟧$ sur le domaine de définition de $⟦{\cal 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 $\bot$ et $\top$ 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' ≝ ⟨ 𝛴^\ast \, ∪ \lbrace \bot, \top \rbrace, +, \cdot, \bot, 𝜀⟩\]

où

  • $+$ est définie, pour tous $w ≠ w’∈𝛴^\ast$, de la manière suivante :

    $+ \; (\nearrow)$ $w$ $w’$ $\bot$ $\top$
    $w$ $w$ $\top$ $w$ $\top$
    $w’$ $\top$ $w’$ $w’$ $\top$
    $\bot$ $w$ $w’$ $\bot$ $\top$
    $\top$ $\top$ $\top$ $\top$ $\top$

  • $\cdot \;$ est la concaténation des mots, prolongée par : $∀w∈𝛴^\ast,$

    • $w \cdot \bot = \bot \cdot w = \bot$
    • $w \cdot \top = \top \cdot w = \top$
    • $\bot \cdot \top = \top \cdot \bot = \bot$

On vérifie que $S’$ est bien un demi-anneau :

  1. $(𝛴^\ast ∪ \lbrace \bot, \top \rbrace, +, \bot)$ est bien un monoïde commutatif

    • $+$ est associative : pour tous $x, y, z ∈ 𝛴^\ast ∪ \lbrace \bot, \top \rbrace$ :

      • Si $x = \top$ ou $y = \top$ ou $z = \top$ :

        \[x + (y + z) = \top = (x + y) + z\]

      • Sinon si $x = \bot$ :

        \[x + (y + z) = y + z = (x + y) + z\]

      • Sinon si $y = \bot$ :

        \[x + (y + z) = x + z = (x + y) + z\]

      • Sinon si $z = \bot$ :

        \[x + (y + z) = x + y = (x + y) + z\]

      • Sinon si $x = y = z$ :

        \[x + (y + z) = x = (x + y) + z\]

      • Sinon :

        \[x + (y + z) = \top = (x + y) + z\]

    • $+$ est commutative (le tableau est symétrique) et d’élément neutre $\bot$

  2. $(𝛴^\ast, \cdot, 𝜀)$ est un monoïde :

    • $\cdot$ est associative : pour tous $x, y, z ∈ 𝛴^\ast ∪ \lbrace \bot, \top \rbrace$ :

      • Si $x = \bot$ ou $y = \bot$ ou $z = \bot$ :

        \[x \cdot (y \cdot z) = \bot = (x \cdot y) \cdot z\]

      • Sinon si $x = \top$ ou $y = \top$ ou $z = \top$ :

        \[x \cdot (y \cdot z) = \top = (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 $𝜀$

  3. $\cdot$ est distributive par rapport à $+$ : pour tous $x, y, z ∈ 𝛴^\ast ∪ \lbrace \bot, \top \rbrace$ :

    • Si $x = \bot$ :

      \[\bot \cdot (y + z) = \bot = \bot \cdot y + \bot \cdot z \\ (y + z) \cdot \bot = \bot = y \cdot \bot + z \cdot \bot \\\]

    • Sinon si $y = z = \bot$ :

      \[x \cdot (y + z) = \bot = x \cdot y + x \cdot z \\ (y + z) \cdot x = \bot = y \cdot x + z \cdot x\]

    • Sinon si $x = \top$ :

      \[\top \cdot (y + z) = \top = \top \cdot y + \top \cdot z \\ (y + z) \cdot \top = \top = y \cdot \top + z \cdot \top\]

      car l’un des deux derniers termes (à droite) vaut $\top$

    • Sinon si $y=z$ ou $z= \bot$ :

      \[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\]

    • Sinon si $y= \bot$ :

      \[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\]

    • Sinon ($x ∈𝛴^\ast, y, z ∈𝛴^\ast ∪ \lbrace \top \rbrace$ et $y≠z$) :

      \[x \cdot (y + z) = x \cdot \top = \top = x \cdot y + x \cdot z \\ (y + z) \cdot x = \top \cdot x = \top = y \cdot x + z \cdot x\]

  4. $\bot$ est absorbant pour $\cdot$

Il s’ensuit qu’en posant :

  • $Q’ ≝ Q$
  • $𝛴’ ≝ 𝛴$
  • $S’ ≝ ⟨ 𝛴^\ast \, ∪ \lbrace \bot, \top \rbrace, +, \cdot, \bot, 𝜀⟩$
\[𝜆'(q) ≝ \begin{cases} m(q) \text{ si } m(q) \text{ est défini} \\ \bot \text{ sinon} \end{cases}\] \[𝛾'(q) ≝ \begin{cases} 𝛾(q) \text{ si } 𝛾(q) \text{ est défini} \\ \bot \text{ sinon} \end{cases}\] \[𝜇(q, a, q') ≝ \begin{cases} (q ⊛ a) \text{ si } q ⟶^a_𝒜 q' \text{ est une transition de } {\cal A} \\ \bot \text{ sinon} \end{cases}\]

alors

\[⟦{\cal A} '⟧(w) ≝ \begin{cases} ⟦{\cal A}⟧(w) \text{ si } ⟦{\cal A}⟧(w) \text{ est défini } \\ \bot \text{ 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 $\bot$ est absorbant, et qu’on n’a qu’un seul chemin au plus dans ${\cal A}$ acceptant $w$, par déterminisme de la fonction séquentielle)

  digraph {
    rankdir=LR;
    subgraph cluster_0{
      label = "𝒜"
      q_0, q_1, q_2;
      b1, b2[style=invis];
    }
    b1 -> q_0[label="m(q_0)"];
    q_0 -> q_0[label="a / q_0 ⊛ a"];
    q_0 -> q_1[label="b / q_0 ⊛ b"];
    q_1 -> q_1[label="a / q_1 ⊛ a"]
    q_1 -> q_2[label="b / q_1 ⊛ b"];
    q_2 -> q_2[label="a, b / q_2 ⊛ a, q_2 ⊛ b"];
    q_2 -> b2[label="𝛾(q_2)"];
  }

⇓

  digraph {
    rankdir=LR;
    subgraph cluster_0{
      label = "𝒜'"
      q_0, q_1, q_2;
      b1, b2, b3[style=invis];
    }
    b1 -> q_0[label="m(q_0)"];
    q_0 -> q_0[label="a / q_0 ⊛ a"];
    q_0 -> q_1[label="b / q_0 ⊛ b"];
    q_1 -> q_1[label="a / q_1 ⊛ a"]
    q_1 -> q_2[label="b / q_1 ⊛ b"];
    q_2 -> q_2[label="a, b / q_2 ⊛ a, q_2 ⊛ b"];
    q_2 -> b2[label="𝛾(q_2)"];
    q_1 -> b3[label="⊥"];
  }

3.

${\cal A} ≝ (𝛴, Q, 𝛿, I, F)$

  digraph {
    rankdir=LR;
    q_2[shape=doublecircle]
    subgraph cluster_0{
      label = "𝒜"
      q_0, q_1, q_2;
    }
    q_0 -> q_0[label="a, b"];
    q_0 -> q_1[label="a"];
    q_1 -> q_2[label="b"];
    q_2 -> q_2[label="a, b"];
  }

⇓

  digraph {
    rankdir=LR;
    q_2[shape=doublecircle]
    subgraph cluster_0{
      label = "𝒜'"
      q_0, q_1, q_2;
    }
    q_0 -> q_0[label="a, b / 1"];
    q_0 -> q_1[label="a / 1"];
    q_1 -> q_2[label="b / 1 "];
    q_2 -> q_2[label="a, b / 1"];
  }

En posant :

  • $Q’ ≝ Q$
  • $𝛴’ ≝ 𝛴$
  • $S’ ≝ ⟨ ℕ, +, ×, 0, 1 ⟩$
\[𝜆'(q) ≝ \begin{cases} 1 \text{ si } q \text{ est initial} \\ 0 \text{ sinon} \end{cases}\] \[𝛾'(q) ≝ \begin{cases} 1 \text{ si } q \text{ est final} \\ 0 \text{ sinon} \end{cases}\] \[𝜇(q, a, q') ≝ \begin{cases} 1 \text{ si } q' ∈ 𝛿(q, a) \\ 0 \text{ sinon} \end{cases}\]

alors

\[⟦{\cal A} '⟧(w) ≝ \sum\limits_{ \underbrace{q_1}_{∈I} ⟶^{w_1}_{\cal A} q_2 ⟶ ⋯ ⟶^{w_n}_{\cal A} \underbrace{q_{n+1}}_{∈F} } \underbrace{1 × ⋯ × 1}_{n+1 \text{ fois}} \\ = \Big\vert\Big\lbrace C ≝ \underbrace{q_1}_{∈I} ⟶^{w_1}_{\cal A} q_2 ⟶ ⋯ ⟶^{w_n}_{\cal A} \underbrace{q_{n+1}}_{∈F} \mid q_i ∈ Q \Big\rbrace \Big\vert \\ = \Big\vert\Big\lbrace C \text{ chemin acceptant étiqueté par } w\Big\rbrace \Big\vert \\ = p_{\cal A}(w)\]

4.

On note $S$ le demi-anneau produit $\lbrace \unicode{x2625}, \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace^{\vert V \vert}$ (non commutatif) muni des lois :

$× \; (\nearrow)$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2753}$ $\unicode{x29B0}$
$\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x29B0}$
$\unicode{x2620}$ $\unicode{x2620}$ $\unicode{x2620}$ $\unicode{x2620}$ $\unicode{x29B0}$
$\unicode{x2753}$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2753}$ $\unicode{x29B0}$
$\unicode{x29B0}$ $\unicode{x29B0}$ $\unicode{x29B0}$ $\unicode{x29B0}$ $\unicode{x29B0}$
$+ \; (\nearrow)$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2753}$ $\unicode{x29B0}$
$\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x2625}$ $\unicode{x2625}$
$\unicode{x2620}$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2620}$ $\unicode{x2620}$
$\unicode{x2753}$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2753}$ $\unicode{x2753}$
$\unicode{x29B0}$ $\unicode{x2625}$ $\unicode{x2620}$ $\unicode{x2753}$ $\unicode{x29B0}$

définies composante par composante, où :

  • $\unicode{x2625}$ sera interprété comme “la variable est vivante”
  • $\unicode{x2620}$ sera interprété comme “la variable est morte”
  • $\unicode{x2753}$ sera interprété comme “la variable est dans un état indéterminé”
  • $\unicode{x29B0}$ 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 $\lbrace \unicode{x2625}, \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace$ et les lois produit correspondantes sur $\lbrace \unicode{x2625}, \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace^{\vert V \vert}$

On vérifie bien que

  • $(S, +)$ est un monoïde commutatif d’élément neutre $\unicode{x29B0}$

  • $(S, ×)$ est un monoïde d’élément neutre $\unicode{x2753}$

  • $×$ est distributive par rapport à $+$ :

    • il suffit de le vérifier composante par composante : pour tous $x, y, z ∈ \lbrace \unicode{x2625}, \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace$ :

      • Si $x = \unicode{x29B0}$ :

        \[\unicode{x29B0} × (y + z) = \unicode{x29B0} = \unicode{x29B0} + \unicode{x29B0} = \unicode{x29B0} × y + \unicode{x29B0} × z \\ (y + z) × \unicode{x29B0} = \unicode{x29B0} = \unicode{x29B0} + \unicode{x29B0} = y × \unicode{x29B0} + z × \unicode{x29B0}\\\]

      • Sinon si $x = \unicode{x2753}$ :

        \[\unicode{x2753} × (y + z) = y + z = \unicode{x2753} × y + \unicode{x2753} × z \\ (y + z) × \unicode{x2753} = y + z = y × \unicode{x2753} + z × \unicode{x2753}\]

      • Sinon si $y = z = \unicode{x29B0}$ :

        \[x × (y + z) = \unicode{x29B0} = x × y + x × z \\ (y + z) × x = \unicode{x29B0} = y × x + z × x\]

      • Sinon :

        \[x × (y + z) = x = x × y + x × z \\ (y + z) × x = y + z = y × x + z × x\]

  • $\unicode{x29B0}$ est absorbant

  • $S$ est borné idempotent :

    • $+$ est idempotent

    • Comme $\unicode{x29B0} \sqsubseteq \unicode{x2753} \sqsubseteq \unicode{x2620} \sqsubseteq \unicode{x2625}$, $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 ≝ (\lbrace \unicode{x2625}, \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace^{\vert V \vert}, +, ×, \unicode{x29B0}, \unicode{x2753})$

Dans la suite, on notera $x_1, \ldots, 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∈ I(V), q, q’∈Q, i∈⟦1,n⟧$ :

\[𝜆(q) ≝ (\unicode{x2753}, \ldots, \unicode{x2753})\] \[𝛾(q) ≝ \begin{cases} (\unicode{x2620}, \ldots, \unicode{x2620}) \text{ si } q = q_f \\ (\unicode{x2753}, \ldots, \unicode{x2753}) \text{ sinon} \end{cases}\] \[𝜇(q, e, q')_i ≝ \begin{cases} \unicode{x2625} &\text{ si } q ⟶^e q' \text{ est une arête de } G \\ &\text{ et } e \text{ est de la forme } \\ &\textsf{if e'(V')} \text{ ou } \textsf{y := e'(V')} \text{ avec } y∈V, x_i∈V' \\ \\ \unicode{x2620} &\text{ sinon si } q ⟶^e q' \text{ est une arête de } G \\ &\text{ et } e \text{ est de la forme } \\ &x_i\textsf{ := e'(V')} \text{ avec } V'⊆V \\ \\ \unicode{x2753} \text{ sinon} \end{cases}\]

Pour tout chemin

\[C ≝ q_{j_1} ⟶^{e_{j_1}} q_{j_2} ⟶^{e_{j_2}} ⋯ ⟶^{e_{j_{m-1}}} q_{j_m} ≝ q_f\]

montrons que la projection sur la $i$-ème composante de $\Vert C \Vert$ permet de déterminer l’état de la variable $x_i$

  • Cas 1 : Si pour tout $k∈⟦1, m-1⟧$, $x_i$ n’apparaît pas dans $e_{j_k}$ :

    alors $x_i$ est morte dans $C$, et :

    \[\begin{align*} \Vert C \Vert &= 𝜆(q_{j_1}) \prod\limits_{ k=1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) 𝛾(q_f) \\ &= (\unicode{x2753}, \ldots, \unicode{x2753}) \Bigg(\prod\limits_{ k=1 }^{m-1} (\unicode{x2753}, \ldots, \unicode{x2753}) \Bigg) (\unicode{x2620}, \ldots, \unicode{x2620}) \\ &= (\unicode{x2620}, \ldots, \unicode{x2620}) \end{align*}\]

    donc on a bien $\Vert C \Vert_i = \unicode{x2620}$

  • 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 $\textsf{if e’(V’)}$ ou $\textsf{y := e’(V’)}$, avec $y∈V, x_i∈V’$ : alors $x_i$ est vivante dans $C$, et :

      \[\begin{align*} \Vert C \Vert_i &= \Bigg[𝜆(q_{j_1}) \prod\limits_{ k=1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) 𝛾(q_f)\Bigg]_i \\ &= \Bigg[\Bigg((\unicode{x2753}, \ldots, \unicode{x2753}) \prod\limits_{ k=1 }^{l-1} \underbrace{𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}})}_{= \; (\unicode{x2753}, \ldots, \unicode{x2753})}\Bigg) \; 𝜇(q_{j_l}, e_{j_l}, q_{j_{l+1}}) \prod\limits_{ k=l+1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) (\unicode{x2620}, \ldots, \unicode{x2620}) \Bigg]_i &&\text{(associativité)}\\ &= \overbrace{\Bigg[\Bigg((\unicode{x2753}, \ldots, \unicode{x2753}) \prod\limits_{ k=1 }^{l-1} \; (\unicode{x2753}, \ldots, \unicode{x2753})\Bigg) \Bigg]_i \quad}^{ = \; \unicode{x2753}} \quad \; \underbrace{\Bigg[ 𝜇(q_{j_l}, e_{j_l}, q_{j_{l+1}}) \Bigg]_i }_{ = \; \unicode{x2625}} \; \Bigg[ \prod\limits_{ k=l+1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) (\unicode{x2620}, \ldots, \unicode{x2620}) \Bigg]_i \\ &= \underbrace{\Bigg[ 𝜇(q_{j_l}, e_{j_l}, q_{j_{l+1}}) \Bigg]_i }_{ = \; \unicode{x2625}} \; \underbrace{\Bigg[ \prod\limits_{ k=l+1 }^{m-1} \underbrace{𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}})}_{ ≠ \unicode{x29B0}} (\unicode{x2620}, \ldots, \unicode{x2620}) \Bigg]_i}_{ ≠ \unicode{x29B0}} \\ &= \unicode{x2625} \end{align*}\]

    • Sous-Cas 2 : si $e_{j_l}$ est de la forme $x_i \textsf{ := e’(V’)}$, avec $V’⊆V$ : alors $x_i$ est morte dans $C$, et :

      \[\begin{align*} \Vert C \Vert_i &= \Bigg[𝜆(q_{j_1}) \prod\limits_{ k=1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) 𝛾(q_f)\Bigg]_i \\ &= \overbrace{\Bigg[\Bigg((\unicode{x2753}, \ldots, \unicode{x2753}) \prod\limits_{ k=1 }^{l-1} \; (\unicode{x2753}, \ldots, \unicode{x2753})\Bigg) \Bigg]_i \quad}^{ = \; \unicode{x2753}} \quad \; \underbrace{\Bigg[ 𝜇(q_{j_l}, e_{j_l}, q_{j_{l+1}}) \Bigg]_i }_{ = \; \unicode{x2620}} \; \Bigg[ \prod\limits_{ k=l+1 }^{m-1} 𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}}) (\unicode{x2620}, \ldots, \unicode{x2620}) \Bigg]_i \\ &= \unicode{x2620} \; \; \underbrace{\Bigg[ \prod\limits_{ k=l+1 }^{m-1} \underbrace{𝜇(q_{j_k}, e_{j_k}, q_{j_{k+1}})}_{ ≠ \unicode{x29B0}} (\unicode{x2620}, \ldots, \unicode{x2620}) \Bigg]_i}_{ ≠ \unicode{x29B0}} \\ &= \unicode{x2620} \end{align*}\]

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

Pour tout sommet $q ∈ Q$, montrons que la projection sur la $i$-ème composante de

\[\Vert q \Vert ≝ \sum\limits_{ C \text{ chemin partant de } q} \Vert C \Vert\]

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{align*} \Vert q \Vert_i & = \underbrace{\Vert C \Vert_i}_{ = \; \unicode{x2625}} \; + \sum\limits_{ C'≠C \text{ chemin partant de } q} \Vert C' \Vert_i \\ &= \unicode{x2625} \end{align*}\]

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 $\Vert q \Vert_i = \unicode{x2625}$ puisque $+(\lbrace \unicode{x2620}, \unicode{x2753}, \unicode{x29B0}\rbrace^2) ⊆ \lbrace \unicode{x2620}, \unicode{x2753}, \unicode{x29B0} \rbrace$, donc une somme d’éléments différents de $\unicode{x2625}$ est différente de $\unicode{x2625}$.

Il vient donc que, pour tout sommet $q$ et chemin $C$, les variables vivantes de $\Vert q \Vert$ et de $\Vert C \Vert$ sont celles dont la coordonnée vaut $\unicode{x2625}$.

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$ :

  1. $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}} ⋯ ⟶^{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

    \[\textsf{if e'(V')} \text{ ou } \textsf{y := e'(V')}\]

    avec $y∈V, x_i∈V’$

  2. $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}} ⋯ ⟶^{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 \textsf{ := e'(V')}\]

      avec $V’⊆V$

    ou

    • $x_i$ n’apparaît dans aucun chemin de $q$ à $q_f$

Si on veut que $\Vert q \Vert_i$ indique l’état de la variable $x_i$ dans l’état $q$, chaque transition $q ⟶^e_G q’$ doit donc vérifier les propriétés suivantes :

  1. $P_\unicode{x2625}\big(q ⟶^e_G q’, i \big)$ :

    si $\Vert q \Vert_i ≠ \unicode{x2625}$ et $e$ est de la forme

    \[\textsf{if e'(V')} \text{ ou } \textsf{y := e'(V')}\]

    avec $y∈V, x_i∈V’$, alors

    \[\Vert q \Vert_i = \unicode{x2625}\]

  2. $P_\unicode{x2620}\big(q ⟶^e_G q’, i \big)$ :

    si $\Vert q \Vert_i ≠ \unicode{x2625}$ et $e$ est de la forme

    \[x_i \textsf{ := e'(V')}\]

    avec $V’⊆V$, alors

    \[\Vert q \Vert_i = \unicode{x2620}\]

  3. $P_\unicode{x2753}\big(q ⟶^e_G q’, i \big)$ :

    si $\Vert q \Vert_i ≠ \unicode{x2625}$ ou $\Vert q’ \Vert_i ≠ \unicode{x2625}$ et $x_i$ n’apparaît pas dans $e$, alors

    \[\Vert q \Vert_i = \Vert q' \Vert_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 $\Vert q \Vert_i$ valent soit $\unicode{x2620}$, soit $\unicode{x2625}$ : les conditions $P_\unicode{x2620}\big(q ⟶^e_G q’, i \big)$ 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 ⟶^e_G q’$ telle que $\Vert q \Vert_i = \unicode{x2625}$ vérifie $P_\unicode{x2625}(t,i)$
  • toute transition $t ≝ q ⟶^e_G q’$ telle que $\Vert q \Vert_i = \Vert q \Vert_i ∈ \lbrace \unicode{x2625}, \unicode{x2620} \rbrace$ vérifie $P_\unicode{x2753}(t,i)$

et chaque $\Vert q \Vert_i$ ne peut être modifié (pour se voir attribuer la valeur $\unicode{x2625}$) qu’au plus une fois dans la boucle principale.

Complexité

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

la complexité de l’algorithme est en

\[O(\vert V \vert \vert Q \vert \vert 𝛿 \vert 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 $\Vert q_f \Vert_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

  digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }
\[I(V) = \Big\lbrace \textsf{x := e(∅)}, \; \textsf{y := e'(x)}, \; \textsf{if e''(x)}, \; \textsf{if ¬ e''(x)}, \; \textsf{x := e'''(x, y)} \Big\rbrace\]

On pose $x_1 ≝ x, x_2 ≝ y$

  • Initialisation :

    $q$ $\Vert q \Vert$
    $q_0$ $(\unicode{x2620}, \unicode{x2620})$
    $q_1$ $(\unicode{x2620}, \unicode{x2620})$
    $q_2$ $(\unicode{x2620}, \unicode{x2620})$
    $q_3$ $(\unicode{x2620}, \unicode{x2620})$
    $q_f$ $(\unicode{x2620}, \unicode{x2620})$ 
      digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☠ , ☠)"];
    q_2[label="q_2\n\n(☠ , ☠)"];
    q_3[label="q_3\n\n(☠ , ☠)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

  • $x_i = x$ :

    • La transition $q_2 ⟶^{\textsf{if ¬ e’‘(x)}} q_f$ ne vérifie pas la propriété $P_\unicode{x2625}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☠ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☠)"];
    q_3[label="q_3\n\n(☠ , ☠)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

    • La transition $q_3 ⟶^{\textsf{x := e’’‘(x, y)}} q_2$ ne vérifie pas la propriété $P_\unicode{x2625}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☠ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☠)"];
    q_3[label="q_3\n\n(☥ , ☠)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

    • La transition $q_1 ⟶^{\textsf{y := e’(x)}} q_2$ ne vérifie pas la propriété $P_\unicode{x2625}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☥ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☠)"];
    q_3[label="q_3\n\n(☥ , ☠)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

  • $x_i = y$ :

    • La transition $q_3 ⟶^{\textsf{x := e’’‘(x, y)}} q_2$ ne vérifie pas la propriété $P_\unicode{x2625}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☥ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☠)"];
    q_3[label="q_3\n\n(☥ , ☥)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

    • La transition $q_2 ⟶^{\textsf{if e’‘(x)}} q_3$ ne vérifie pas la propriété $P_\unicode{x2753}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☥ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☥)"];
    q_3[label="q_3\n\n(☥ , ☥)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

    • La transition $q_2 ⟶^{\textsf{if e’‘(x)}} q_3$ ne vérifie pas la propriété $P_\unicode{x2753}$ :

        digraph {
    rankdir=LR;
    q_f[shape=doublecircle];
    b[style=invis];
    q_0[label="q_0\n\n(☠ , ☠)"];
    q_1[label="q_1\n\n(☥ , ☠)"];
    q_2[label="q_2\n\n(☥ , ☥)"];
    q_3[label="q_3\n\n(☥ , ☥)"];
    q_f[label="q_f\n\n(☠ , ☠)"];
    b -> q_0;
    q_0 -> q_1[label="  x := e(∅)"];
    q_1 -> q_2[label=" y := e'(x)"];
    q_2 -> q_3[label=" if e''(x)"];
    q_3 -> q_2[label="x := e'''(x, y)"];
    q_2 -> q_f[label="if ¬ e''(x)"];
  }

Sortie :

$q$ $\Vert q \Vert$
$q_0$ $(\unicode{x2620}, \unicode{x2620})$
$q_1$ $(\unicode{x2625}, \unicode{x2620})$
$q_2$ $(\unicode{x2625}, \unicode{x2625})$
$q_3$ $(\unicode{x2625}, \unicode{x2625})$
$q_f$ $(\unicode{x2620}, \unicode{x2620})$

Propriétés de clôture

6.

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

Alors en posant :

\[{\cal A}_h ≝ (Q, 𝛴, S, 𝜆', 𝜇', 𝛾')\]
  • $𝜆’ ≝ h \circ 𝜆$
  • $𝛾’ ≝ h \circ 𝛾$
  • $𝜇’ ≝ h \circ 𝜇$

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

\[\begin{align*} ⟦{\cal A}_h⟧(w) &= 𝜆' 𝜇'(w) 𝛾' \\ & = (h \circ 𝜆) (h \circ 𝜇)(w) (h \circ 𝛾) \\ &= h \circ (𝜆 𝜇(w) 𝛾) &&\text{puisque } h \text{ respecte les lois de } S\\ & = h(⟦{\cal A}⟧(w)) \\ & = h(f)(w) \end{align*}\]

Donc

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

5.

Soient $f: 𝛴^\ast ⟶ S$ et $g: 𝛴^\ast ⟶ S$ deux fonctions reconnues respectivement par des automates pondérés ${\cal A}_f$ et ${\cal A}_g$.

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

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

\[\begin{align*} (f + g)(w) &= f(w) + g(w)\\ & = ⟦{\cal A}_f⟧(w) + ⟦{\cal A}_g⟧(w) \\ &= 𝜆_f 𝜇_f(w) 𝛾_f + 𝜆_g 𝜇_g(w) 𝛾_g \end{align*}\]

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: 𝛴^\ast ⟶ S$ et $g: 𝛴^\ast ⟶ S$ deux fonctions reconnues respectivement par des automates pondérés ${\cal A}_f$ et ${\cal A}_g$, et $(S, +, ×)$ un demi-anneau commutatif.

Rappels sur le produit de Kronecker $\otimes$ :

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

\[A\otimes B ≝ \begin{pmatrix}a_{11}B&\cdots &a_{1n}B\\\vdots &\ddots &\vdots \\a_{m1}B&\cdots &a_{mn}B\end{pmatrix} \\ = \begin{pmatrix}a_{11}b_{11}&a_{11}b_{12}&\cdots &a_{11}b_{1q}&\cdots &\cdots &a_{1n}b_{11}&a_{1n}b_{12}&\cdots &a_{1n}b_{1q}\\a_{11}b_{21}&a_{11}b_{22}&\cdots &a_{11}b_{2q}&\cdots &\cdots &a_{1n}b_{21}&a_{1n}b_{22}&\cdots &a_{1n}b_{2q}\\ \vdots &\vdots &\ddots &\vdots &&&\vdots &\vdots &\ddots &\vdots \\a_{11}b_{p1}&a_{11}b_{p2}&\cdots &a_{11}b_{pq}&\cdots &\cdots &a_{1n}b_{p1}&a_{1n}b_{p2}&\cdots &a_{1n}b_{pq}\\\vdots &\vdots &&\vdots &\ddots &&\vdots &\vdots &&\vdots \\ \vdots &\vdots &&\vdots &&\ddots &\vdots &\vdots &&\vdots \\a_{m1}b_{11}&a_{m1}b_{12}&\cdots &a_{m1}b_{1q}&\cdots &\cdots &a_{mn}b_{11}&a_{mn}b_{12}&\cdots &a_{mn}b_{1q}\\a_{m1}b_{21}&a_{m1}b_{22}&\cdots &a_{m1}b_{2q}&\cdots &\cdots &a_{mn}b_{21}&a_{mn}b_{22}&\cdots &a_{mn}b_{2q}\\ \vdots &\vdots &\ddots &\vdots &&&\vdots &\vdots &\ddots &\vdots \\a_{m1}b_{p1}&a_{m1}b_{p2}&\cdots &a_{m1}b_{pq}&\cdots &\cdots &a_{mn}b_{p1}&a_{mn}b_{p2}&\cdots &a_{mn}b_{pq}\end{pmatrix}\]

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)=(AC)\otimes (BD)\]

Montrons que $f×g$ est reconnaissable.

On note $n$ (resp. $m$) le nombre d’états de ${\cal A}_f$ (resp. ${\cal A}_g$).

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

\[\begin{align*} (f × g)(w) &= \underbrace{f(w)}_{∈S} × \underbrace{g(w)}_{∈S} \\ & = \underbrace{f(w)}_{∈S} \otimes \underbrace{g(w)}_{∈S} &&\text{(les éléments de } S \text{ sont vus }\\ & && \text{comme des matrices 1×1)}\\ &= (𝜆_f 𝜇_f(w) 𝛾_f) \otimes (𝜆_g 𝜇_g(w) 𝛾_g) \\ & = \big(𝜆_f \otimes 𝜆_g\big) \big(𝜇_f(w) \otimes 𝜇_g(w)\big) \big(𝛾_f \otimes 𝛾_g \big) &&\text{(produit mixte, car } S \text{ est commutatif)}\\ & = \begin{pmatrix} 𝜆_{f,1} 𝜆_{g, 1} \\ \vdots \\ 𝜆_{f,1} 𝜆_{g, m}\\ \vdots \\ 𝜆_{f,n} 𝜆_{g, 1} \\ \vdots \\ 𝜆_{f,n} 𝜆_{g, m} \end{pmatrix} \begin{pmatrix}𝜇_{f,11}(w) 𝜇_g(w)&\cdots & 𝜇_{f,1n}(w) 𝜇_g(w)\\ \vdots &\ddots &\vdots \\ 𝜇_{f,n1}(w) 𝜇_g(w) &\cdots & 𝜇_{f,nn}(w) 𝜇_g(w) \end{pmatrix} \begin{pmatrix} 𝛾_{f,1} 𝛾_{g, 1} \\ \vdots \\ 𝛾_{f,1} 𝛾_{g, m}\\ \vdots \\ 𝛾_{f,n} 𝛾_{g, 1} \\ \vdots \\ 𝛾_{f,n} 𝛾_{g, m} \end{pmatrix}\\ & = ⟦{\cal A}_{f × g}⟧(w) \end{align*}\]

en posant \({\cal A}_{f × g} ≝ (Q', 𝛴, S, 𝜆', 𝜇', 𝛾')\)

où

  • $Q’ ≝ Q_f × Q_g$

  • $∀q∈ Q_f, q’∈Q_g, \quad 𝜆’((q, q’)) ≝ 𝜆_f(q) × 𝜆_g(q’)$

  • $∀q∈ Q_f, q’∈Q_g, \quad 𝛾’((q, q’)) ≝ 𝛾_f(q) × 𝛾_g(q’)$

  • $∀a∈ 𝛴, q_1, q_2∈ Q_f, q’_1, q’_2∈Q_g,
    \quad 𝜇’((q_1, q’_1), a , (q_2, q’_2)) ≝ 𝜇_f(q_1, a, q_2) × 𝜇_g(q’_1, a, q’_2)$

Donc

si $f$ et $g$ sont reconnaissables et si $S$ est commutatif, $f × 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 ≝ ⟨ ℙ(𝛴^\ast), ∪, \cdot, ∅, \lbrace 𝜀 \rbrace ⟩$ et sur l’alphabet $𝛴 ≝ \lbrace a, b \rbrace$.

La fonction $f$ définie sur tout mot $w ∈𝛴^\ast$ par

\[f(w) ≝ \lbrace w \rbrace\]

est clairement reconnaissable.

Mais ce n’est pas le cas de $f×f ≝ w \mapsto \lbrace w \rbrace \cdot \lbrace w \rbrace = \lbrace w^2 \rbrace$.

Par l’absurde, si ${\cal A} ≝ (Q, 𝛴, S, 𝜆, 𝜇, 𝛾)$ à $N ≝ \vert Q \vert$ états reconnaissait $f×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 ⋯ ⟶^b \underbrace{q_{j_m}}_{∈F}$ é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≥1, l≥0$ tels que

  • $k+l+r = N+1$
  • le même chemin où on a bouclé $n$ fois sur $q_{j_k} ⟶^a ⋯ ⟶^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) = \lbrace a^{N+1}b a^{N+1}b \rbrace$

  • $f^2(a^k (a^r)^n a^l b) = \lbrace a^k (a^r)^n a^l b a^k (a^r)^n a^l b \rbrace = \lbrace u v^n w \rbrace$

    • où $uvw = 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×g$ n’est pas nécessairement reconnaissable.

Leave a comment