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

Automates à double sens

Automate Boustrophédon :: $B = ⟨ Q, 𝛴 ⊔ {▹, ◃} ⟩, I, F, 𝛿 ⟩$

$𝛿 \subseteq Q \times (𝛴 ⊔ {▹, ◃}) \times {⟵, ⟶} \times Q$

Configuration :

(u, q, v) : u, v \in (▹ 𝛴^{*} \times 𝛴^{*} ◃), q \in Q

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

Ex :

(u, q, a v) ⟶^{(q, a, d, q^{'})} (u^{'}, q^{'}, v^{'})

si $d =⟶$ , $u^{'} = u a, v^{'} = v$

𝜆_{0}^{0}, 𝜆_{0}^{1}, 𝜆_{1}^{1}, 𝜆_{1}^{0} : 𝛴^{*} ⟶ 2^{Q \times Q}

w \sim w^{'} ⟺ \forall i, j \in {0, 1}, 𝜆_{j}^{i} (w) = 𝜆_{j}^{i} (w^{'})

Cette relation d’équivalence est une congruence.

Preuve :

Si $u \sim u^{'}$ et $v \sim v^{'}$ , montrons que

\forall (p, q) \in Q \times Q, (p, q) \in 𝜆_{0}^{1} (u v) ⟺ (p, q) \in 𝜆_{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^{'} \in 𝛴^{*}$ , et $w \in 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^{'} \in L$ aussi.

Normalisation d’automates séquentiels

$f : A^{*} ⟶ A^{*}$

f (a^{2 n} b) = (a b)^{n} a

\begin{matrix} m_{1} = a \\ m_{2} = a \\ m_{3} = 𝜀 \end{matrix}

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

Normalisation

⇓

i ⊛^{'} a = m_{i}^{- 1} (i ⊛ a) m_{i ⊙ a}

\begin{matrix} 1 ⊛^{'} a = m_{1}^{- 1} (1 ⊛ a) m_{1 ⊙ a} = m_{1}^{- 1} (1 ⊛ a) m_{2} = a^{- 1} (a b) a = b a \\ 2 ⊛^{'} a = a^{- 1} (𝜀) a = 𝜀 \\ 1 ⊛^{'} b = a^{- 1} (a) 𝜀 = 𝜀 \end{matrix}

\begin{matrix} m_{1}^{'} = 𝜀 \\ m_{2}^{'} = 𝜀 \\ m_{3}^{'} = 𝜀 \end{matrix}

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 (a b)^{- 1}$ :

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

\begin{matrix} m_{𝜀} = ⋀ {b \dots, a \dots, a b \dots} = 𝜀 \\ m_{a} = 𝜀 \\ m_{a b} = 𝜀 \end{matrix}

Automates à piles déterministes

L = {a^{n} b a^{n} ∣ n \geq 0}

Abréviations :

$D$ : déterministe
$T R$ : en temps réel = sans $𝜀$ -transition
$S$ : standardisé

On veut calculer les $m_{i}$ :

{\begin{cases} X_{1} = a b X_{1} + a b a X_{1} + a b X_{3} \\ X_{2} = X_{1} + a b X_{4} \\ X_{3} = X_{1} + a b X_{4} \\ X_{4} = a b X_{2} + a b a b \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^{*} \cup {0}$ .

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} = a b, u = b a$ : $(v_{1} + v_{2}) u = a u = a b a \neq v_{1} u + v_{2} u = a b a + a b b a = a b$

On note $\leq$ l’ordre (partiel) préfixe sur $k$ (avec $u \leq 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^{*} b X_{1}$
$X_{1} = a X_{1} + b X_{2} + 𝜀 = a X_{1} + b a^{*} b X_{1} + 𝜀 = (a + b a^{*} b) X_{1} + 𝜀$
⟹ $X_{2} = a^{*} b (a + b a^{*} b)^{*}$

Lemme d’Arden

Soit une équation sur les langages d’inconnue $X$ :
$X = K X + L$
alors $X = K^{*} L$

Preuve :

Si $X$ est une solution, alors :

X = K X + L ⟹ {\begin{cases} L \subseteq X \\ K X \subseteq X \end{cases} ⟹ K \underset{\subseteq X}{\underset{⏟}{L}} \subseteq X

Donc $K^{2} X \subseteq X$ , et par récurrence $K^{*} L \subseteq X$

Réciproquement :

Mq $X \subseteq K^{*} L$ .

Soit $w$ le mot le plus court de $X ∖ K^{*} L$ .

w \notin L ⟹ w \in K X

Donc $w ≝ \underset{\in K}{\underset{⏟}{u}} \underset{\in X}{\underset{⏟}{v}}$

Comme $u \neq 𝜀$ , $v$ est plus court que $w$ , donc $v \in K^{*} L$ , et

w \in K^{+} L \subseteq K^{*} L

contradiction.

Exemple :

{\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 + b a)^{*} b b (a + b)^{*}

Donné :

\begin{matrix} L_{0} = a^{*} b (a + b)^{*} + b a^{*} \\ = \underset{≝ K}{\underset{⏟}{a^{*}}} \underset{≝ L}{\underset{⏟}{b (a + b)^{*}}} \end{matrix}

\begin{matrix} L_{0} = a L_{0} + b \underset{L_{1}}{\underset{⏟}{(a + b)^{*}}} \\ = a L_{0} + b L_{1} \end{matrix}

L_{1} = (a + b) L_{1} + 𝜀

Share on

Twitter Facebook Google+ LinkedIn