TD 13 : Langages déterministes, acceptation par pile vide, acceptation généralisée, non-ambiguïté

EX 1

1.

Lemme d’Ogden :

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

Soit $L ⊆ 𝛴^\ast$ déterministe. Il existe un entier $N$ tq $∀w∈L$ avec $N$ lettres distinguées, $w$ se factorise en

\[w ≝ 𝛼 u 𝛽 v 𝛾\]

tq

  1. $∀p≥0, \; 𝛼 u^p 𝛽 v^p 𝛾$

  2. $u 𝛽 v$ contient moins de $N$ lettres distinctes

  3. soit $𝛼, u, 𝛽$ soit $𝛽, v, 𝛾$ contiennent des lettres distinguées

  4. pour tout $𝛾’∈𝛴^\ast$,

\[∃p; \; 𝛼u^p 𝛽 v^p 𝛾' ∈ L \\ ⟹ ∀ p, 𝛼 u^p 𝛽 v^p 𝛾' ∈ L\]

2.

Montrons que $L_1 ∪ L_2$ n’est pas déterministe.

Jeu à deux joueurs :

  • l’adversaire propose $N$
  • nous nous proposons le mot $w$ et les lettres distinguées, et l’adversaire essaye de nous bloquer (il veut qu’on soit obligé de remplir le 4ème point sachant que les 3 premiers le sont) en propos
  • l’adversaire propose une factorisation
  • nous nous proposons un $𝛾’$ ne satisfaisant pas 4).

  1. Nous : pour le $N$ donné par l’adversaire, on propose \(w = a^N c b^N\) (où les $a$ sont distingués)

  2. Pour tout découpage $w = 𝛼u𝛽v𝛾$ satisfaisant 1, 2, 3, on a :

    • $u = a^K, v = b^K$, pour un $0<k < N$

  3. Le point 3 est vérifié :

    • on vérifie que $v$ ne peut pas contenir de lettre distinguée ⟹ $𝛼, u, 𝛽$ doit contenir des lettres distinguées

      • $𝛼≠𝜀$
      • $u = a^k, k>0$
      • $𝛽$ contient la lettre $c$

  4. on considère $𝛾’ = 𝛾 b^N$, alors \(𝛼 u^1 𝛽 v^1 𝛾' ∈ = \underbrace{𝛼 u^1 𝛽 v^1 𝛾}_{∈L_1}𝛼 u^1 𝛽 v^1 𝛾 b^N L_2\)

    mais $𝛼𝛽𝛾’ ∉ L_1 ∪ L_2$ (car $\underbrace{2N-k}{\text{ nombre de } b} ∉ \underbrace{\lbrace N-k, 2(N-k) \rbrace}{\text{ nombres possibles de } a}$ ) donc la condition 4 n’est pas remplie, et $L_1 ∪ L_2$ n’est pas déterministe.

3.

Les langages déterministes sont clos par complémentation, et

\[L_1 ∩ L_2 = \overline{\overline{L_1} ∪ \overline{L_2}}\]

donc ils ne sont pas clos par intersection.

4.

On complète l’automate et on inverse les états finaux et les états initiaux.

EX 2

1.

Soit $L$ déterministe

  1. si $L$ est préfixe alors il existe un AAPD qui accepte $L$ par pile vide

  2. si $L$ n’est pas préfixe, alors un tel AAPD n’existe pas.

Si $L$ n’est pas préfixe, alors il existe $w$ et $ww’$ dans $L$ avec $w’ ≠𝜀$.

Soit $L$ un langage hors-contexte.

Montrons que

il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$ si, et seulement si $L$ est déterministe et préfixe.

$⟹$ :

Supposons qu’il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$.

Montrons que $L$ est déterministe et préfixe.

$L$ est déterministe

On construit, de la même manière que dans le cours, l’automate à pile suivant :

\[{\cal A}' ≝ ⟨Q \sqcup \lbrace q_f \rbrace, 𝛴, 𝛤 \sqcup \lbrace \bot \rbrace, 𝛿', q_0, \bot z_0, \lbrace q_f \rbrace ⟩\]

où

\[𝛿' ≝ 𝛿 ∪ \lbrace (q, \bot, 𝜀, q_f, 𝜀) \mid q∈F \rbrace\] 
  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="𝒜'"
    subgraph cluster_1 {
      label="𝒜"
        q_1[style=dashed]; q_2[style=dashed]; q_3[style=dashed]; ⋯;
    }
    ⊥z_0;q_f[shape="doublecircle"];
  }
    q_f[shape="doublecircle"];
    ⊥z_0 -> ⋯;
    ⋯ -> {q_1, q_2, q_3};
    q_1 ->q_f[label="𝜀, ⊥/𝜀"];
    q_2 ->q_f[label="𝜀, ⊥/𝜀"];
    q_3 ->q_f[label="𝜀, ⊥/𝜀"];
  }

NB : on rajoute un nouveau fond de pile $\bot$, et pour chaque $q∈Q$ tel que la pile est “vide” (avec notre nouveau fond), on ajoute l’$𝜀$-transition $q, \bot \overset{𝜀}{⟶} q_f, 𝜀$

On a démontré en cours que

\[L({\cal A}') = N({\cal A})\]

De plus, ${\cal A}’$ est clairement déterministe, puisque pour tous $(q, z)) ∈ Q \sqcup \lbrace q_f \rbrace × 𝛤 \sqcup \lbrace \bot \rbrace$ :

  • si $q = q_f$ : aucune transition ne part de $q$

  • sinon, si $q∈Q$ :

    • si $z∈𝛤$ : les transitions partant de $(q, z)$ sont celles de ${\cal A}$, qui est déterministe.

    • si $z = \bot$ : la seule transition qui part de $(q, \bot)$ est l’$𝜀$-transition $(q, \bot, 𝜀, q_f, 𝜀)∈𝛿’$

Donc $L$ est déterministe.

$L$ est préfixe

Si n’était pas le cas, il existerait un mot $w ≝ w_1 \underbrace{w_2}_{\text{de longueur }≥1} ∈ L$ avec $w_1∈L$.

Par conséquent, comme $L = N({\cal A})$, il existerait $q_1, q_1’, q_2∈ Q$ tels que :

\[\begin{cases} q_0, z_0 \overset{w_1}{⟶}_{\cal A} q_1, 𝜀 \quad \text{(car } w_1∈L \text{)}\\ q_0, z_0 \overset{w_1}{⟶}_{\cal A} q_1', 𝛾 \overset{w_2}{⟶^+}_{\cal A} q_2, 𝜀 \quad \text{(car } w_2∈L \text{ et } \vert w_2 \vert > 0 \text{)}\\ \end{cases}\]

Mais alors le déterminisme de ${\cal A}$ impliquerait :

\[\begin{cases} q_1' = q_1 \\ 𝛾 = 𝜀 \end{cases}\]

Et

\[q_1, 𝜀 \overset{w_2}{⟶^+}_{\cal A} q_2, 𝜀\]

devient alors absurde puisque qu’aucune transition ne peut partir de $(q_1, 𝜀)$, car la pile est vide.

Le résultat est donc acquis.

$⟸$ :

Supposons qu’il existe un DPDA ${\cal A}’ ≝ ⟨Q’, 𝛴’, 𝛤’, 𝛿’, q_0’, z_0’, F’⟩$ reconnaissant $L$ et que $L$ est préfixe.

Montrons qu’il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$.

Notons déjà qu’on peut supprimer toutes les transitions sortant d’un état final de ${\cal A}’$ sans changer le langage reconnu par ${\cal A}’$ (qui reste $L$) puisque $L$ est préfixe :

En effet : montrons que pour toute exécution de la forme

\[q_0', z_0' \overset{w_1}{⟶}_{\cal A'} \underbrace{q_F'}_{∈F'}, 𝛾_F' \overset{w_2}{⟶^+}_{\cal A'} q_2', 𝛾_2' \quad \text{(avec } \vert w_2 \vert > 0 \text{)}\]

nécessairement : $w_1 w_2∉ L({\cal A’})=L$.

Par l’absurde : si $w_1 w_2∈ L({\cal A’})=L$, alors comme $w_1∈L$ (puisque $q_0', z_0' \overset{w_1}{⟶}_{\cal A'} \underbrace{q_F'}_{∈F'}, 𝛾_F'$) et $\vert w_2 \vert>0$, $L$ ne serait pas préfixe.

Pour ne pas alourdir les notations, on note encore ${\cal A}’ ≝ ⟨Q’, 𝛴’, 𝛤’, 𝛿’, q_0’, z_0’, F’⟩$ l’automate obtenu en supprimant toutes les transitions sortant d’un état final.

On construit alors, de la même manière que dans le cours, l’automate à pile (qui accepte par pile vide) suivant :

\[{\cal A} ≝ ⟨Q' \sqcup \lbrace q_f \rbrace, 𝛴', 𝛤' \sqcup \lbrace \bot \rbrace, 𝛿, q_0', \bot z_0'⟩\]

où

\[𝛿 ≝ 𝛿' ∪ \lbrace (q,z, 𝜀, q_f, 𝜀) \mid q∈F'\sqcup \lbrace q_f \rbrace, z∈𝛤' \sqcup \lbrace \bot \rbrace \rbrace\] 
  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="𝒜"
    subgraph cluster_1 {
      label="𝒜'"
        q_1[label="q_1'", shape=doublecircle, style=dashed]; q_2[label="q_2'", shape="doublecircle", style=dashed]; q_3[label="q_3'", shape="doublecircle", style=dashed]; ⋯;
    }
    ⊥z_0[label="⊥z_0'"]; q_f;
  }
    ⊥z_0 -> ⋯;
    ⋯ -> {q_1, q_2, q_3};
    q_1 ->q_f[label="𝜀, z/𝜀"];
    q_2 ->q_f[label="𝜀, z/𝜀"];
    q_3 ->q_f[label="𝜀, z/𝜀"];
    q_f -> q_f[label="𝜀, z/𝜀"]
  }

NB : on rajoute un nouveau symbole de fond de pile $\bot$, et on ajoute des $𝜀$-transitions partant des anciens états finals vers un nouvel état $q_f$ qui vide la pile.

On a démontré en cours que

\[N({\cal A}) = L({\cal A}') = L\]

De plus, ${\cal A}$ est déterministe, puisque pour tous $(q, z, b) ∈ Q’ \sqcup \lbrace q_f \rbrace × 𝛤’ \sqcup \lbrace \bot \rbrace × 𝛴$ :

  • si $q = q_f$ : la seule transition partant de $(q, z)$ est l’$𝜀$-transition $(q_f, z, 𝜀, q_f, 𝜀)$.

  • sinon, si $q∈Q’\backslash F’$ :

    • si $z∈𝛤’$ : les transitions partant de $(q, z)$ sont celles de ${\cal A}’$, qui est déterministe.

    • si $z = \bot$ : aucune transition ne part de $(q, \bot)$.

  • sinon, si $q∈ F’$ :

    comme on a supprimé toutes les transitions sortant d’un état final dans ${\cal A}’$, la seule transition qui part de $(q, z)$ est l’$𝜀$-transition $(q, z, 𝜀, q_f, 𝜀)∈𝛿’$

Donc le résultat est acquis.

On a donc montré que

Pour tout langage hors-contexte $L$, il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$ si, et seulement si $L$ est déterministe et préfixe.

M2 :

2.

  1. $D_n^\ast$ est déterministe

  2. $D_n^\ast$ peut-il être accepté par un AAPD par pile vide ? Non, car le lanagage n’est pas préfixe.

Grammaire :

\[S ⟶ a_1 S \overline{a_1} S \mid ⋯ \mid a_n S \overline{a_n} S \mid 𝜀\] 
  digraph {
    rankdir=TB;
    q_0[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_1[label=" a_i, x/x A_1^0"];
    q_1 -> q_1[label="a_i, x/x A_i | a'_i, A_i/𝜀"];
    q_1 -> q_0[label="a'_i, A_i^0/𝜀"];
  }

3.

Soit $A ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0 z_0, K⟩$ où $K ⊆ Q 𝛤^\ast$ rationnel.

$A$ accepte $w ∈ 𝛴^\ast$ ssi

\[𝛿^\ast(q_0 z_0, w) ∈K\]

  • avec par état : $K = F 𝛤^\ast$

  • avec pile vide : $K = Q$

On cherche un AAPD qui accepte par état final et tq $L(A’) = L(A)$

NB : Pour les langages algébriques, cette condition est équivalente aux autres : si on a un tel automate, on construit un automate fini reconnaissant $K$, et on ajoute des $𝜀$-transitions vers l’automate à pile pour vérifier à chaque étape l’état de la pile (destructif ⟶ on ne peut pas reconstituer la pile après, d’où le non-déterminisme)

\[K \text{ rationnel } ⟺ K^t \text{ rationnel }\]
\[A' = ⟨QxS, 𝛴, 𝛤 × S, 𝛿', c_0 ≝ ⟨q_0, 𝜂(s_0, z_0)⟩⟨z_0, s_0⟩ , F'⟩\]

Soit $B = ⟨S, 𝛤∪ Q, 𝜂, S_0, F⟩$ un automate fini déterministe reconnaissant $\widetilde{K} = K^R$

Soit $q a_1 ⋯ a_n$ une configuration de $A$. Alors il existe un seul chemin dans $B$ de la forme

\[s_0 ⟶^{a_n} s_1 ⟶_{a_{n-1}} ⟶ ⋯ ⟶^{a_1} s_n ⟶^q s_{n+1}\]

Configurations de $A$ : $∈ Q’ (𝛤’^\ast)$

Si, dans $A$, $𝛿(q_0 z_0, w) = q a_1 ⋯ a_n$ ⟶ quelle est la traduction dans $A’$?

\[⟨q, s_n⟩ ⟨a_1, s_{n-1}⟩ ⋯ ⟨a_n, s_0⟩\] \[F' ≝ \lbrace (q, s) \mid 𝜂(s, q) ∈ F \rbrace\]

Pour tout $(q, 𝛾, a)$ dans $Q × 𝛤 × (𝛴 ∪ \lbrace 𝜀 \rbrace)$

  • si $𝛿(q, 𝛾, a) = q’,𝜀$, alors pour tous $s, s’ ∈ S$,

    \[𝛿(⟨q, s⟩, ⟨𝛾, s'⟩, a) = ⟨q', s'⟩\] \[q 𝛾 a_2 ⋯ a_n \\ q' a_2 ⋯ a_n\]

    $\downarrow$

    \[⟨q, s_n⟩ ⟨𝛾, s_{n-1}⟩ ⟨a_2, s_{n-2}⟩ ⋯ \\ ⇓ \\ ⟨q', 𝜂(s_{n-2}, a)⟩ ⟨a_2, s_{n-2}⟩ ⋯ \\\]

  • si $𝛿(q, 𝛾, a) = q’, 𝛾’$ pour tout $s, s’∈S$ :

    \[𝛿'(⟨q, s⟩, ⟨𝛾, s'⟩, a) = ⟨q', 𝜂(s', 𝛾')⟩⟨𝛾', s'⟩\]

  • si $𝛿(q, 𝛾, a) = q’ 𝛾’ 𝛾’’$ etc… analogue

Leave a comment