TD 12 : Fonctions séquentielles, Automates à pile déterministes

EX 1

1.

$𝜙 : A^\ast ⟶ A^\ast$

\[𝜙(a^{3n}b) = (ab)^n a\] 
  digraph {
    rankdir=LR;
    blank2[label=""];
    ""-> 1[label="𝜀"];
    2 -> 3[label="a / 𝜀"];
    3 -> 1[label="a / 𝜀"];
    1 -> 2[label="a / ab"];
    1 -> 4[label="b / a"];
    4 -> blank2[label="𝜀"];
  }
\[m_1 = a\\ m_2 = a \\ m_3 = a \\ m_4 = 𝜀\]

($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_1=a"];
    2 -> 3[label="a / 𝜀"];
    3 -> 1[label="a / 𝜀"];
    1 -> 2[label="a / ba"];
    1 -> 4[label="b / 𝜀"];
    4 -> blank2[label="𝜀"];
  }
Entrée Sortie
$b$ $a$
$a^3b$ $aba$
$a^6b$ $ababa$
  1. plus grand préfixe commun des sorties : $a$

(on le supprime)

⇓

Entrée Sortie
$b$ $𝜀$
$a^3b$ $ba$
$a^6b$ $baba$
  1. plus grand préfixe commun des sorties dont l’entrée commence par :

  • $a$ : $ba$

  • $b$ : $𝜀$

(on le supprime)

⇓

Entrée Sortie
$a^3b$ $𝜀$
$a^6b$ $ba$
  1. plus grand préfixe commun des sorties dont l’entrée commence par :
  • $aa$ : $𝜀$

(on le supprime)

⇓

Entrée Sortie
$a^6b$ $ba$
$a^9b$ $baba$

plus grand préfixe commun des sorties dont l’entrée commence par :

  • $aaa$ : $ba$

et on retombe sur $ba$ (on boucle)

\[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 = 𝜀\\ 3 ⊛' a = a^{-1} (𝜀) a = 𝜀\\ 1 ⊛' b = a^{-1} (a) 𝜀 = 𝜀\]

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

2.

On complète l’automate normalisé précédent :

  digraph {
    rankdir=LR;
    blank2[label=""];
    ""-> 1[label="a"];
    2 -> 3[label="a / 𝜀"];
    2 -> d[label="b / 𝜀"];
    3 -> d[label="b / 𝜀"];
    4 -> d[label="a / 𝜀"];
    d -> d[label="a,b / 𝜀"];
    3 -> 1[label="a / 𝜀"];
    1 -> 2[label="a / ba"];
    1 -> 4[label="b / 𝜀"];
    4 -> blank2[label="𝜀"];
  }
\[L = \lbrace a^{3n}b \mid n≥0 \rbrace\] \[u∈ dom(f_𝜀) = dom(f) \\ f_𝜀(u) = \Big( \bigwedge f(A^\ast) \Big)^{-1} f(u) \\ = a^{-1} f(u)\]
\[u∈ dom(f_a) = \lbrace a^{3n-1} b \mid n≥1 \rbrace \\ f_a(u) = \Big( \bigwedge f(a A^\ast) \Big)^{-1} f(au) \\ = a^{-1} b^{-1} a^{-1} f(au)\]
\[u∈ dom(f_{aa}) = \lbrace a^{3n-2} b \mid n≥1 \rbrace \\ f_{aa}(u) = a^{-1} b^{-1} a^{-1} f(aau)\]
\[u∈ dom(f_{aaa}) = \lbrace a^{3n} b \mid n≥0 \rbrace \\ f_{aaa}(u) = a^{-1} b^{-1} a^{-1} \underbrace{f(aaau)}_{(ab) f(u)} \\ = a^{-1} f(u)\]
\[f_𝜀 = f_{aaa} = f_{a^{3n}}\]
\[u∈ dom(f_b) = b^{-1} dom(f) = \lbrace 𝜀 \rbrace \\ f_b(𝜀) = a^{-1} f(b) = a^{-1} a = 𝜀\] 
  digraph {
    rankdir=LR;
    blank1[label=""];
    ""-> "f𝜀"[label="a"];
    "f𝜀" -> "fa"[label="a / ba"];
    "fa" -> "faa"[label="a / 𝜀"];
    "faa" -> "f𝜀"[label="a / 𝜀"];
    "faa" -> "fab"[label="b / 𝜀"];
    "fab" -> "fab"[label="a,b / 𝜀"];
    "f𝜀" -> "fb"[label="b / 𝜀"];
    "fb" -> "fab"[label="a, b / 𝜀"];
    "fa" -> "fab"[label="b / 𝜀"];
    "fb" -> blank1[label="𝜀"];
  }

EX 2

\[L_1 = \lbrace a^n c b^n \mid n>0 \rbrace \\ L_2 = \lbrace a^n c b^{2n} \mid n>0 \rbrace\]

1.

$𝒜_1 :$

  digraph {
    rankdir=LR;
    q_f[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xA"];
    q_0 -> q_1[label="c, x/x"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
  }

$𝒜_2 :$

  digraph {
    rankdir=LR;
    q_f[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xAA"];
    q_0 -> q_1[label="c, x/x"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
  }

Pour montrer que

\[L_1 ∪ L_2 = \lbrace a^n c b^n \mid n>0 \rbrace ∪ \lbrace a^n c b^{2n} \mid n>0 \rbrace\]

n’est pas déterministe, on utilise le lemme d’itération.

2.

On complète $𝒜_1$ :

  digraph {
    rankdir=LR;
    q_f[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xA"];
    q_0 -> q_1[label="c, x/x"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
    q_0 -> d[label="b, x/x"];
    q_1 -> d[label="a, x/x"];
    q_f -> d[label="a,b, x/x"];
    d -> d[label="a,b, x/x"];
  }

Puis on inverse les états finals et initiaux :

$𝒜_1^c :$

  digraph {
    rankdir=LR;
    q_1, q_0, d[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xA"];
    q_0 -> q_1[label="c, x/x"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
    q_0 -> d[label="b, x/x"];
    q_1 -> d[label="a, x/x"];
    q_f -> d[label="a,b, x/x"];
    d -> d[label="a,b, x/x"];
  }

Leave a comment