TD 10 : Reconnaissance par morphisme, machines de Moore et automates de Mealy

Énoncé

EX 1 : Reconnaissance par morphisme

Si $(M_1, ×_1, e_1), (M_2, ×_2, e_2)$ sont des un mononoïdes et $f_1, f_2$ des morphismes tels que :

  • $f_1^{-1}(f_1(L_1)) = L_1$
  • $f_2^{-1}(f_2(L_2)) = L_2$

$L_1^c$ est reconnu par morphisme

En effet : le même $f_1$ reconnaît $L_1^c$, puisque

\[𝛴^\ast \backslash L = 𝛴^\ast \backslash f^{-1}(f(L)) \\ = f^{-1}(f(𝛴^\ast \backslash L))\]

$L_1∩L_2$ est reconnu par morphisme

On pose

  • $f_1(L_1) = M’_1$
  • $f_2(L_2) = M’_2$

On note $M_{int} = M_1 × M_2$ le morphisme produit.

On note $𝜑$ le morphisme défini par $r: 𝛴^\ast \ni w \mapsto (f_1(w), f_2(w)) ∈ M_{int}$

On vérifie aisément que :

\[r^{-1}(r(L_1 ∩ L_2)) = L_1 ∩ L_2\]

$L_1∪L_2$ est reconnu par morphisme

\[L_1∪L_2 = (L_1^c ∩ L_2^c)^c\]

EX 2 : Langages apériodiques

Monoïde apériodque :

s’il existe $n∈ℕ$ tq pour tout $x∈M$,

\[x^n = x^{n+1}\]
Un langage $L$ est dit apériodique :

s’il est reconnu par un morphisme apériodique

Ex :

  • $L = (ab)^\ast$
  • $𝛴 = \lbrace a, b \rbrace$
  • $M = (L, La, bLa, \bot)$
a/b L La bLa ⊥
L L La ⊥ ⊥
La        
bLa        
⊥        

\(L' ≝ (aa)^\ast\) n’est pas apériodique

Preuve :

Soit $M$ un monoïde et $f : \lbrace a, b \rbrace^\ast ⟶ M$ un morphisme reconnaissant $L’$.

Soit $n$ un entier tq pour tout $x∈M$,

\[x^{n+1} = x^n\]

Soit $x = f(a)$.

Alors :

\[x^{n+1} = f(a^{n+1}) = f(a^n) = x^n\]

conduit à une contradiction, puisque l’un deux mots parmi $a^{n+1}$ et $a^n$ est dans $L$, et l’autre est dans $L^c$.

\[FO(𝛴, <) = P_{\underbrace{a}_{∈𝛴}}(x) \mid 𝜑 ∧ 𝜓 \mid ¬ 𝜑 \mid x < y \mid ∀x. 𝜑\] \[L'_3 = ac^\ast b\]

est défini par la formule du premier ordre

\[∀y. (¬first(y) ∧ ¬last(y) ⟹ P_c(y))\\ ∧ ∃x. first(x) ∧ P_a(x)\\ ∧ ∃z. last(z) ∧ P_b(z)\]
\[L''_3 = (ac^\ast b)^\ast\]

est défini par la formule du premier ordre $𝜑 = 𝜑_a ∧ 𝜑_b ∧ 𝜑_c ∧ 𝜑_{vide} ∧ 𝜓$

où

\[𝜑_a ≝ ∀x. P_a(x) ⟹ (first(y) ∨ (∃y. next(y, x) ∧ P_b(y)))\\ ∧ (∃ y. next(x,y) ∧ (P_c(y) ∨ P_b(y)))\] \[𝜑_b ≝ ∀x. P_b(x) ⟹ (last(x) ∨ (∃y. next(x, y) ∧ P_a(y)))\\ ∧ (∃ y. next(y,x) ∧ (P_a(y) ∨ P_c(y)))\]

$𝜑_c$ analogue

\[𝜑_{vide} = ¬ ∃ x. first(x)\] \[𝜓 = ∃x. first(x) ∧ P_a(x) \\ ∃x. last(x) ∧ P_b(x)\]

EX 3 : Machines de Moore et automates de Mealy

1.

Moore ⟶ Mealy

Etant donné $M = ⟨Q, A, B, q_0, \odot, 𝛾⟩$.

On construit $A ≝ ⟨Q, A, B, q_0, m=𝜀, \odot, ⊛_A, 𝜌_A⟩$ tel que

\[⟦M⟧ = ⟦A⟧\]

et

\[𝜌_A ≝ \begin{cases} Q ⟶ B^\ast \\ q \mapsto 𝛾(q) \end{cases}\] \[⊛_A ≝ \begin{cases} Q × A ⟶ B^\ast \\ q, a \mapsto 𝛾(q) \end{cases}\] 
  digraph {
    rankdir=LR;
    a[style=dashed];
    a -> bb[label="0"];
    bb -> a[label="1"];
  }

$\downarrow$

  digraph {
    rankdir=TB;
    1[style=dashed];
    end1, end2[label=""];
    1 -> 2[label="0/a"];
    2 -> 1[label="1/bb"];
    1 -> end1[label="a"];
    2 -> end2[label="bb"];
  }
\[A' ≝ ⟨Q, A, B, q_0, 𝛾(q_0), \odot, ⊛_{A'}, 𝜌_{A'}⟩\]

$∀q∈Q, 𝜌_{A’} = 𝜀$

\[⊛_{A'} ≝ \begin{cases} Q × A ⟶ B^\ast \\ q, a \mapsto 𝛾(\odot(q,a)) \end{cases}\]

2.

Mealy ⟹ Moore

Soit $D = f(⊛)∪ \lbrace 𝜀 \rbrace$, alors $D$ est fini.

\[M = ⟨Q × D, A, B, <q_0, 𝜀>, \odot_M, 𝛾_M⟩\]

  • $𝛾_M(<q, w>)=w$

  • $\odot_M(<q, w>, a) = <\odot(q,a), ⊛(q,a)>$

  digraph {
    rankdir=TB;
    1[style=dashed];
    end1, end2[label=""];
    1 -> 2[label="0/a"];
    2 -> 1[label="1/bb"];
    1 -> end1[label="a"];
    2 -> end2[label="bb"];
  }

$\downarrow$

  digraph {
    rankdir=LR;
    "1,𝜀"[style=dashed];
    "1,𝜀" -> "2,a"[label="0"];
    "2,a" -> "1,bb"[label="1"];
    "1,bb" -> "2,a"[label="0"];
  }

Mais FS non pure $\not⟶$ Moore

\[⟨ \lbrace q \rbrace, \lbrace a \rbrace, \lbrace b, c \rbrace, q, 𝜀, \odot, ⊛, 𝜌⟩\]

avec

  • $\odot(q, a) = q$
  • $⊛(q, a) = b$
  • $𝜌(q) = c$
\[⟦A⟧(a^n) = b^nc\]

mais ne peut pas être représenté par une machine de Moore :

  • à un seul état : le langage est $(𝛾(q))^\ast$

  • à $n$ états : principe des tiroirs, la sortie de $a^{n+1}$ est de la forme $b^nc$.

    Or : le dernier état $q$ rencontré vérifie $𝛾(q)=c$, mais comme il a déjà été rencontré avant, il vérifie aussi $𝛾(q)=b$

EX 4

\[B ≝ \lbrace 0, 1 \rbrace\] \[∀w∈B^\ast, g : B^\ast ⟶ ℕ\]

la valeur naturelle, notée par $w$ en notation binaire

Ex :

  • $g(10101)=21$
  • $g(10)= 2$

On s’intéresse à $f : B^\ast ⟶ B^\ast$ tq

\[f(w) = g^{-1}(g(w)^2)\]

Ex :

  • $f(10) = 100$
  • $f(1001) = 1010001$

Th : Si $f : A^\ast ⟶ B^\ast$ est séquentielle est $L⊆A^\ast$ est rationnel, alors $f(L)$ est rationnel aussi.

Par l’absurde, supposons que $f$ est séquentielle.

Remarquons que :

\[f(1 ⋯ 1) = g^{-1}((2^n - 1)^2) = g^{-1}(2^n(2^{n-1} - 1)+1) \\ = \underbrace{1⋯1}_{n-1 \text{ fois}} \; \underbrace{0 ⋯ 0 1}_{n \text{ fois}}\]

Or avec $L ≝ 1^+$ :

\[f(L) ≝ \lbrace \underbrace{1⋯1}_{n-1 \text{ fois}} \; \underbrace{0 ⋯ 0 }_{n \text{ fois}} 1 \mid n ∈ℕ\rbrace\]

n’est pas rationnel : contradiction avec le théorème.

Leave a comment