TD 8 : Accessibilité dans les grammaires algébriques

Énoncé

Chargé de TD : Stefan Schwoon.

EX 1

  digraph {
    rankdir=LR;
    q_0[shape="doublecircle"];

    subgraph cluster_0 {
      label="𝒜"
      q_f;
    }
    q_f -> q_0[label="𝜀"];
    q_0 -> q_0[label="u∈𝛺"];
    q_0 -> puits_q[label="q∈Q"];
    puits_q -> q_0[label="q_bar ∈Q_bar"];

  }

1.

Si $𝒜_L = ⟨Q_L, 𝛺, 𝛿_L, q_{0, L}, F_L⟩$ est un automate reconnaissant $L$.

On pose

\[𝛿_L' ≝ \Big\lbrace (q_L, v, q'_L) \mid ∃n≥0; q_1, ⋯, q_n ∈ Q ∪ 𝛤 \, ; \; q_L \overset{q_1 ⋯ q_n \overline{q_n} ⋯ \overline{q_1} v}{⟶}_{𝒜_L} \, q'_L \Big\rbrace\]

Alors l’automate

\[𝒜' ≝ ⟨Q_L, 𝛺, 𝛿'_L, q_{0, L}, F_L⟩\]

reconnaît $Clot(L)$.

---

  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      q_i, q_j, q_1, q_2;
    }
    q_1, q_2, q_3[label=""];

    "" -> q_i[label="u", style = "dashed"];
    q_i-> q_1[label="a"];
    q_i -> q_j[label="𝜀"];
    q_1 -> q_2[label="𝜀*", style="dashed"];
    q_2 -> q_j[label="a_bar"];
    q_j -> q_3[label="v", style="dashed"];


  }

Soit

\[B ≝ (S, 𝛺, 𝜂, s_0, G)\]

un automate fini tq $L(B) = L$

Soit $𝜂’$ le plus petit ensemble tq

\[𝜂 ∪ \left\lbrace (s,𝜀, t) \mid ∃a∈ Q∪𝛤, s', t'∈S; \begin{cases} (s, a, s')∈ 𝜂' ∧ s' \overset{𝜀}{⟶}^\ast_{𝜂'} t' \\ (t', \overline{a}, t) ∈ 𝜂' \end{cases} \right\rbrace\]

Mq $B’ ≝ (S, 𝛺, 𝜂’, s_0, G)$ accepte $Clot(L)$.

$Clot(L)⊆ L(B’)$

C’est facile, par construction.

$L(B’) ⊆ Clot(L)$

On construit $𝜂’$ itérativement :

• $𝜂_0 ≝ 𝜂$
• $𝜂_{i+1} ≝ 𝜂_i ∪ \lbrace (q_{i+1}, 𝜀, q’_{i+1}) \rbrace$
• $\vdots$
• $𝜂_K ≝ 𝜂’$ pour $K$ assez grand

Puis, on pose :

\[B_i ≝ (S, 𝛺, 𝜂_i, s_0, G)\]

On prouve par réc. sur $i$ que

\[L(B_i) ⊆ Clot(L)\]

• Pour $i=0$ : $L⊆Clot(L)$

• Pour $i>0$ :

Si $s_0 ⟶^w s_G$ est un chemin acceptant dans $B_{i+1}$, on note $j$ le nombre d’occurrences de $(q_{i+1}, 𝜀, q’_{i+1})$ dans ce chemin.

Par réc sur $j$ :

• Pour $j=0$ : ok car $L(B_i) ⊆ Clot(L)$ par HR

• Pour $j+1$ :

\[s_0 \overset{u}{⟶}_{B_{i+1}}^\ast q_{i+1} ⟶^𝜀_{B_{i+1}} q'_{i+1} \overset{v}{⟶}_{B_{i+1}}^\ast s_G\]

avec $uv = w$

Alors :

\[s_0 \overset{u}{⟶}_{B_{i+1}}^\ast q_{i+1} \underbrace{⟶^a_{B_{i+1}} \overset{𝜀}{\leadsto}^\ast ⟶^{\overline{a}}_{B_{i+1}} }_{∈𝜂_i} q'_{i+1} \overset{v}{⟶}_{B_{i+1}}^\ast s_G\]

Par hypothèse de réc, $ua \overline{a} v ∈ Clot(L)$, donc $uv=w$ aussi.

2.

\[q, 𝛾 \overset{n}{⟶} q', 𝛾'\]

ssi

\[q, 𝛾 \overset{a_1 ⋯ a_n}{⟶} q', 𝛾'\]

ssi

\[\begin{align*} \underbrace{q_0}_{= q}, \underbrace{𝛾_0}_{= 𝛾} &\overset{a_1}{⟶} q_2, 𝛾_2 \\ & \vdots \\ &\overset{a_n}{⟶} \underbrace{q_n}_{= q'}, \underbrace{𝛾_n}_{=𝛾'} \\ \end{align*}\]

---

$⟹$

Par réc sur $n∈ℕ^\ast$.

• Pour $n=1$ :

Si $q, 𝛾 \overset{a}{⟶} q’, 𝛾’’$

alors

• $𝛾 = \widetilde{𝛾} z$
• $𝛾’ = \widetilde{𝛾} z’’$

Par déf de $K$ :

\[\overline{q}\overline{z} 𝛾'' q'∈K\]

Soit :

\[𝛾q\overline{q} \overline{z} 𝛾'' q' = \widetilde{𝛾} z q\overline{q} \overline{z} 𝛾'' q' \leadsto^2 \widetilde{𝛾} 𝛾'' q' = 𝛾'q'\]

L’hérédité est immédiate.

$⟸$

Si $∃w∈K$ tq

\[𝛾 q \overline{p} \overline{z} 𝛾'' q'' \leadsto^2 𝛾' q'\]

où $w = \overline{p} \overline{z} 𝛾’’ q’’$

Nécessairement :

• $p=q$ et $𝛾 = \widetilde{𝛾} z$

Donc

\[w = \overline{q} \overline{z} 𝛾'' q'' ∈ K ⟹ ∃a; (q, z, q, q'', 𝛾'') ∈ 𝛿\]

Par simplification :

\[𝛾qw \leadsto^2 \widetilde{𝛾} 𝛾'' q'' = 𝛾'q' ⟹ \begin{cases} \widetilde{𝛾} 𝛾'' = 𝛾' \\ q'' = q' \end{cases}\]

On conclut que

\[q, 𝛾 ⟶^a q', 𝛾'\]

L’hérédité est immédiate.

3.

\[C(p, 𝛾) ≝ \lbrace ⟨p', 𝛾'⟩ \mid p,𝛾 ⟶^+ p', 𝛾' \rbrace \\ = Clot(𝛾pK^+) ∩ 𝛤^\ast Q\]

( par 2) )

• $𝛾pK^+$ est régulier, d’alphabet $𝛺$

  • donc d’après 1) : $Clot(𝛾pK^+)$ est régulier

• $𝛤^\ast Q$ est régulier

• les langages réguliers sont clos par intersection.

Donc

$C(p, 𝛾)$ est régulier.

4.

ATTENTION : pour cette question, on change d’interprétation : la tête de pile est désormais à gauche.

$L’⊆ Q 𝛤^\ast$ régulier

\[\overline{C}(L') ≝ \lbrace q𝛾' ∈ Q𝛤^\ast \mid q, 𝛾' ⟶^\ast p, 𝛾 \text{ pour } p, 𝛾∈L'\rbrace\]

NB : Dans la question précédente, la taille de l’automate construit est considérable. On propose maintenant une nouvelle méthode qui construit un automate ayant le même nombre d’états.

Pour $𝒜$ un automate de pile, $Q$ des états, et $𝛤$ alphabet de pile.

Un $𝒜$-automate :

un automate fini de la forme $B ≝ (S, 𝛤, 𝜂, Q, F)$ tel que $L(B) ≝ \lbrace qw \mid q∈Q, w∈𝛤^\ast, q \overset{w}{⟶}^\ast q_f \text{ avec } q_f∈F\rbrace$

Construire $B$ avec

\[L(B) = L'\]

Rajouter des transitions à $B$ selon la règle suivante :

si $(p, a, 𝜎, q, 𝛾’)$ est une transition dans $𝒜$ et

\[q \overset{𝛾'}{⟶}^\ast q'\]

dans $B$ pour un $q’$ quelconque,

on rajoute $(p, a, q’)$ dans $B$.