TD 2 : Dérivées partielles, Antimirov, Glushkov

Énoncé

EX 1

1.

Non, par le lemme de l’étoile par blocs, car sinon : il existe $N∈ℕ$ tel que tout

\[u ≝ \underbrace{𝜀}_{u} 0^N \underbrace{1^N}_{v}∈L(𝒜)\]

est tel que

\[u ≝ 𝜀 0^{N-l} (0^{l-k})^\ast 0^{k} 1^N⊆L(𝒜)\]

c’est absurde

2.

Non, par le lemme de l’étoile par blocs : idem à précédemment.

3.

Oui :

$𝒜$ :

  digraph {
    rankdir=LR;
    ⋯2[label="⋯",shape=doublecircle];
    f[label="1337",shape=doublecircle];
    f1[label="1",shape=doublecircle]
    0 -> 1[label="0"];
    1 -> ⋯[label="0"];
    ⋯ -> 1337[label="0"];
    1337 -> 1337[label="0"];
    1337 -> f1[label="1"];
    f1 -> ⋯2[label="1"];
    ⋯2 -> f[label="1"];
  }

4.

BIT DE POIDS FORT À DROITE !

écriture binaire $\mod 3$ si $\overline{x}$ est de longueur paire $\mod 3$ si $\overline{x}$ est de longueur impaire  
  $\overline{x0}$ $x \mod 3$ $x \mod 3$
  $\overline{x1}$ $x + (-1)^{2\vert \overline{x} \vert} = x \mod 3$ $x + (-1)^{2\vert \overline{x} \vert} = x - 1 \mod 3$

$𝒜$ :

  digraph {
    rankdir=LR;
    0p[label="0 pair",shape=doublecircle];
    1p[label="1 pair"];
    2p[label="2 pair"];
    0i[label="0 impair",shape=doublecircle];
    1i[label="1 impair"];
    2i[label="2 impair"];
    0i -> 0p[label="0"];
    1i -> 1p[label="0"];
    2i -> 2p[label="0"];
    0p -> 0i[label="0"];
    1p -> 1i[label="0"];
    2p -> 2i[label="0"];
  }

EX 2

1.

\[\partial_a((ab+b)^\ast ba) = \lbrace b(ab+b)^\ast ba \rbrace\]
  • tout $w∈\partial_a((ab+b)^\ast ba)$ est suffixe d’un mot commençant par $ab$ : c’est donc un mot commençant par $b$, concaténé avec un mot de $(ab+b)^\ast ba$, d’où le résultat.
\[\partial_b((ab+b)^\ast ba) = \lbrace (ab+b)^\ast ba, a\rbrace\]

  • tout $w∈\partial_a((ab+b)^\ast ba)$ est suffixe d’un mot commençant par :

    • $ba$ : alors c’est le mot $a$.
    • $bb$ : c’est donc un mot commençant par $b$, concaténé avec un mot de $(ab+b)^\ast ba$, d’où le résultat.

2.

Prop :

\[L(\partial_a(E)) = a^{-1} L(E)\]

Par induction sur $E$ :

  • Si $E=∅$ :

$\partial_a(E) = ∅$, et $a^{-1} L(E) = ∅$

donc

$L(\partial_a(E)) = ∅ = a^{-1} L(E)$

  • Si $E=b$ :

    • Si $b=a$ :

      $\partial_a(E) = \lbrace 𝜀 \rbrace$, et $a^{-1} L(E) = 𝜀$

    • Sinon si $b≠a$ :

      $\partial_a(E) = ∅$, et $a^{-1} L(E) = ∅$

  • Si $E = E’+E’’$ :

\[\partial_a(E) = \partial_a(E') ∪ \partial_a(E'')\]

et

\[a^{-1} L(E) = a^{-1} L(E') ∪ a^{-1} L(E'')\]

donc le résultat est acquis par induction.

  • Si $E = E’ \cdot E’’$ :

    • Si $𝜀 \not ∈ E’$ :

      \[\partial_a(E) = \partial_a(E'). \lbrace E'' \rbrace\]

      et

      \[a^{-1} L(E) = a^{-1} L(E') \cdot L(E'')\]

    • Si $𝜀 ∈ E’$ :

      \[\partial_a(E) = \partial_a(E'). \lbrace E'' \rbrace ∪ \partial_a(E'')\]

      et

      \[a^{-1} L(E) = a^{-1} L(E') \cdot L(E'') ∪ a^{-1} L(E'')\]

donc le résultat est acquis par induction.

  • Si $E = E’^\ast$ :

    idem.

Prop :

\[L(\partial_w(E)) = w^{-1} L(E)\]

Par induction sur $\vert w \vert$

\[L(\partial_{wa} (E)) = L(\partial_{a} (\partial_{w} E)) \\ = \bigcup\limits_{E'∈\partial_{w}(E)} L(\partial_a (E')) = \bigcup\limits_{E'∈\partial_{w}(E)} a^{-1} L(E') \\ = a^{-1} L(\partial_{w}(E)) = a^{-1} w^{-1} L(E) \\ = (wa)^{-1}L(E)\]

3.

  digraph {
    rankdir=LR;
    LE[label="L(E)"];
    aLE[label="a^{-1}L(E)"];
    bLE[label="b^{-1}L(E)"];
    acLE[label="{ac}^{-1}L(E)"];
    adLE[label="{ad}^{-1}L(E)"];
    LE -> aLE[label="a"];
    LE -> bLE[label="b"];
    aLE -> acLE[label="c"];
    aLE -> adLE[label="d"];
  }

Les états finaLS sont les états étiquetés par des langages contenant $𝜀$.

4.

\[Suf(w) = \lbrace v ∈ 𝛴^\ast \mid ∃u; w = uv\rbrace\]

Montrer les résultats suivants pour $w∈𝛴^+$ :

\[\begin{align*} \partial_w(E+E') &= \partial_w(E) ∪ \partial_w(E') \\ \partial_w(E \cdot E') &⊆ (\partial_w(E) \cdot E') ∪ \bigcup\limits_{v∈Surf(w)} \partial_v(E') \\ \partial_w(E^\ast) &⊆ \bigcup\limits_{v∈Suf(w)} \partial_v(E) \cdot E^\ast \\ \end{align*}\]
\[\partial_w(E+E') = \partial_w(E) ∪ \partial_w(E')\]

Par induction sur $\vert w \vert$ :

L’initialisation est claire.

Hérédité : si $w= w’ a$

\[\partial_w(E+E') = \partial_a(\partial_w'(E+E')) \\ = \partial_a(\partial_w'(E) ∪ \partial_w'(E')) \\ = \bigcup\limits_{E''∈\partial_w'(E) ∪ \partial_w'(E')} \partial_a(E'') \\ = \bigcup\limits_{E''∈\partial_w'(E)} \partial_a(E'') ∪ \bigcup\limits_{E''∈ \partial_w'(E')} \partial_a(E'') \\ = \partial_a(\partial_w'(E)))∪\partial_a(\partial_w'(E')))\]

et le résultat est acquis.

\[\partial_w(E \cdot E') ⊆ (\partial_w(E) \cdot E') ∪ \bigcup\limits_{v∈Suf(w)} \partial_v(E')\]

Si $E’‘∈ \partial_w(E \cdot E’)$, on procède de même.

\[\partial_w(E^\ast) ⊆ \bigcup\limits_{v∈Suf(w)} \partial_v(E) \cdot E^\ast\]

Par induction sur $\vert w \vert$ :

  • si $w=a$ :
\[\partial_a(E^\ast) = \partial_a(E) \cdot E^\ast\]

et $Suf(a) = \lbrace a \rbrace$

  • Si $w = w’a$ :
\[\partial_{w'a}(E^\ast) = \partial_a(\partial_w'(E^\ast)) \\ ⊆ \partial_a\Big(\bigcup_{v∈Suf(w)} \partial_v(E) \cdot E^\ast\Big) \\ = \bigcup\limits_{E'∈ \bigcup_{v∈Suf(w)} \partial_v(E) \cdot E^\ast }\partial_a(E') \\ = \bigcup\limits_{E'∈ \bigcup_{v∈Suf(w)} \partial_v(E) }\partial_a(E' \cdot E^\ast) \\ ⊆ \bigcup\limits_{E'∈ \bigcup_{v∈Suf(w)} \partial_v(E) }\partial_a(E') \cdot E^\ast\\\]

Or : si $E’∈ \bigcup_{v∈Suf(w)} \partial_v(E)$, il existe $v’∈Suf(w)$ tel que

\[E' ≝ \partial_v'(E)\]

et alors :

\[\partial_a(E') = \partial_a(\partial_v'(E)) = \partial_{\underbrace{v'a}_{∈Suf(w)}}(E)\]

5.

Par induction sur $E$ :

\[\bigcup_{w∈𝛴^+} \partial_w(E) ≤ \Vert E \Vert\]

Leave a comment