Cours 8 : Automates à double sens, Automates séquentiels

Automates à double sens

Automate Boustrophédon :
\[B = ⟨Q, 𝛴 \sqcup \lbrace \triangleright, \triangleleft \rbrace⟩, I, F, 𝛿⟩\]
  • \[𝛿 ⊆ Q × (𝛴 \sqcup \lbrace \triangleright, \triangleleft \rbrace) × \lbrace ⟵, ⟶ \rbrace × Q\]

Configuration :

\[(u, q, v) : u, v∈ (\triangleright 𝛴 ^\ast × 𝛴^\ast \triangleleft), q∈Q\]

C’est une machine de Turing qui n’écrit pas sur son ruban.

Ex :

\[(u, q, av)⟶^{(q, a, d, q')} (u', q', v')\]
  • si $d = ⟶$, $u’ = ua, v’= v$
\[𝜆_0^0, 𝜆_0^1, 𝜆_1^1, 𝜆_1^0 : 𝛴^\ast ⟶ 2^{Q×Q}\] \[w \sim w' ⟺ ∀i,j∈ \lbrace 0, 1 \rbrace, 𝜆^i_j (w) = 𝜆^i_j (w')\]

Cette relation d’équivalence est une congruence.

Preuve :

Si $u \sim u’$ et $v \sim v’$, montrons que

\[∀(p, q)∈Q×Q, (p, q)∈ 𝜆_0^1(u v) ⟺ (p, q)∈ 𝜆_0^1(u' v')\]

Il suffit de concaténer les chemins de $u$ (qui sont les mêmes que $u’$) aux chemins de $v$ (qui sont les mêmes que $v’$).

Elle sature $L$

En effet, si $w, w’∈𝛴^\ast$, et $w∈L$ on découpe un chemin acceptant en sous-chemins allant d’un bout de la bande à l’autre, et chacun de ces sous-chemins ont un équivalent dans $w’$ par congruence, d’où $w’∈L$ aussi.

Normalisation d’automates séquentiels

$f : A^\ast ⟶ A^\ast$

\[f(a^{2n}b) = (ab)^n a\] 
  digraph {
    rankdir=LR;
    blank2[label="", style=invis];

    ""-> 1[label="𝜀"];
    2 -> 1[label="a / 𝜀"];
    1 -> 2[label="a / ab"];
    1 -> 3[label="b / a"];
    3 -> blank2[label="𝜀"];
  }
\[m_1 = a\\ m_2 = a \\ m_3 = 𝜀\]

($m_i$ : plus long préfixe commun des sorties qu’on peut écrire à partir de l’état $i$)

Normalisation

⇓

  digraph {
    rankdir=LR;
    blank2[label=""];
    ""-> 1[label="m=a"];
    2 -> 1[label="a / 𝜀"];
    1 -> 2[label="a / ba"];
    1 -> 3[label="b / 𝜀"];
    3 -> blank2[label="𝜀"];
  }
\[i ⊛' a = m_i^{-1} (i ⊛ a) m_{i \odot a}\] \[1 ⊛' a = m_1^{-1} (1 ⊛ a) m_{1 \odot a} = m_1^{-1} (1 ⊛ a) m_2 = a^{-1} (ab) a = ba\\ 2 ⊛' a = a^{-1} (𝜀) a = 𝜀\\ 1 ⊛' b = a^{-1} (a) 𝜀 = 𝜀\]

et

\[m'_1 = 𝜀\\ m'_2 = 𝜀 \\ m'_3 = 𝜀\]

Les sorties sont font plus tôt ⟶ pour écrire la même chose sur la sortie, on lit moins de lettres.

Automates des résiduels pour $f(w) = w(ab)^{-1}$ :

(fonction partielle : elle enlève un suffixe $ab$ si le mot $w$ en a un)

  digraph {
    rankdir=LR;
    1[label="fab", shape=doublecircle];
    2[label="fa"];
    3[label="f𝜀", style=dashed];
    2 -> 1[label="b / 𝜀"];
    1 -> 2[label="a / ab"];
    1 -> 3[label="b / b"];
    3 -> 2[label="a / 𝜀"];
    2 -> 2[label="a / a"]
    3 -> 3[label="b / b"];
  }
\[m_𝜀 = \bigwedge \lbrace b ⋯, a ⋯, ab ⋯ \rbrace = 𝜀\\ m_a = 𝜀\\ m_{ab} = 𝜀\]

Automates à piles déterministes

\[L = \lbrace a^n b a^n \mid n≥0 \rbrace\] 
  digraph {
    rankdir=LR;
    q_f[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xA"];
    q_0 -> q_1[label="b, x/x"];
    q_1 -> q_1[label="a, A/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
  }

Abréviations :

  • $D$ : déterministe
  • $TR$ : en temps réel = sans $𝜀$-transition
  • $S$ : standardisé
  digraph {
    blank[label=""];
    "" -> 1;
    1 -> 1[label="ab"];
    1 -> 2[label="aba"];
    2 -> 1[label="𝜀"];
    1 -> 3[label="ab"];
    3 -> 1[label="𝜀"];
    3 -> 4[label="ab"];
    4 -> 2[label="ab"];
    2 -> 4[label="b"];
    4 -> blank[label="abab"];
  }

On veut calculer les $m_i$ :

\[\begin{cases} X_1 = ab X_1 + aba X_1 + ab X_3\\ X_2 = X_1 + ab X_4 \\ X_3 = X_1 + ab X_4 \\ X_4 = ab X_2 + abab \\ \end{cases}\]

où

  • les $X_i$ sont les mots $m_i$
  • $+$ est l’opération “plus grand préfixe commun” ($0$ : élément neutre).

On travaille dans le semi-anneau à gauche : $k ≝ A^\ast ∪ \lbrace 0 \rbrace$.

On observe que :

  • $u+0 = 0+u = u$
  • $u+u =u$

  • il y a distributivité à gauche mais par pas à droite : \(u(v_1 + v_2) = u v_1 + u v_2\)

    • pas de distributivité à droite (exemple de Maher ) : si $v_1 = a, v_2 = ab, u = ba$ : \((v_1 + v_2) u = au = aba ≠ v_1 u + v_2 u = a ba + abba = ab\)

On note $≤$ l’ordre (partiel) préfixe sur $k$ (avec $u ≤ 0$ par convention). On l’étend à $k^n$ composante par composante.

La multiplication est la concaténation.

https://www.irif.fr/~jep/PDF/Exposes/Sequential.pdf

\[\begin{cases} X_1 = a X_1 + b X_2 + 𝜀\\ X_2 = b X_1 + a X_2 \end{cases}\]
  • $X_2 = a^\ast b X_1$

  • $X_1 = a X_1 + b X_2 + 𝜀 = a X_1 + ba^\ast b X_1 + 𝜀 = (a+ba^\ast b)X_1 + 𝜀$

  • ⟹ $X_2 = a^\ast b (a + ba^\ast b)^\ast$

Lemme d’Arden

Soit une équation sur les langages d’inconnue $X$ :

\[X = KX + L\]

alors $X = K^\ast L$

Preuve :

Si $X$ est une solution, alors :

\[X = KX + L ⟹ \begin{cases} L ⊆ X \\ KX ⊆ X \end{cases} ⟹ K\underbrace{L}_{⊆X} ⊆ X\]

Donc $K^2 X ⊆ X$, et par récurrence $K^\ast L ⊆ X$

Réciproquement :

Mq $X ⊆ K^\ast L$.

Soit $w$ le mot le plus court de $X \backslash K^\ast L$.

\[w ∉ L ⟹ w ∈ KX\]

Donc \(w ≝ \underbrace{u}_{∈K}\underbrace{v}_{∈X}\)

Comme $u ≠ 𝜀$, $v$ est plus court que $w$, donc $v∈K^\ast L$, et

\[w ∈ K^+ L ⊆ K^\ast L\]

contradiction.

Exemple :

  digraph {
    rankdir=LR;
    blank[label="", style=invis];
    q_2[shape=doublecircle];
    blank -> q_0;
    q_0 -> q_0[label="a"];
    q_0 -> q_1[label="b"];
    q_1 -> q_0[label="a"];
    q_1 -> q_2[label="b"];
    q_2 -> q_2[label="a, b"];

  }
\[\begin{cases} L_0 = a L_0 + b L_1 \\ L_1 = a L_0 + b L_2 \\ L_2 = a L_2 + b L_2 + 𝜀 \\ \end{cases}\] \[L_0 = (a+ba)^\ast bb (a+b)^\ast\]

Donné :

\[L_0 = a^\ast b (a+b)^\ast + ba^\ast \\ = \underbrace{a^\ast}_{ ≝ K} \underbrace{b (a+b)^\ast}_{ ≝ L}\] \[L_0 = a L_0 + b \underbrace{(a+b)^\ast}_{L_1} \\ = a L_0 + b L_1\] \[L_1 = (a+b) L_1 + 𝜀\] 
  digraph {
    rankdir=LR;
    blank[label="", style=invis];
    1[shape=doublecircle];
    blank -> 0;
    0 -> 0[label="a"];
    0 -> 1[label="b"];
    1 -> 1[label="a,b"];

  }

Leave a comment