TD 1 : Introduction

Énoncé

Chargée de TD : Marie FORTIN

EX 1

1.

$𝒜_1$ :

  digraph {
    rankdir=LR;
    0 -> 1[label="a"];
    0 -> 0[label="a,b"];
    1 -> 2[label="b"];
    2 -> 3[label="a"];
  }

\[L(𝒜_1) = (a+b)^\ast aba\]

DFA :

  digraph {
    rankdir=LR;
    0 -> 0[label="b"];
    0 -> 1[label="a"];
    1 -> 0[label="a"];
    1 -> 2[label="b"];
    2 -> 0[label="b"];
    2 -> 3[label="a"];
    3 -> 0[label="a,b"];
  }

---

  digraph {
    rankdir=LR;
    0 -> 1[label="a"];
    0 -> 0[label="a,b"];
    1 -> 2[label="a,b"];
    2 -> 3[label="a,b"];
  }

\[L(𝒜_2) = (a+b)^\ast a (a+b)^2\]

DFA :

  digraph {
    rankdir=LR;
    0 -> 0[label="b"];
    0 -> 1[label="a"];
    1 -> 0[label="a"];
    1 -> 2[label="a,b"];
    2 -> 3[label="a,b"];
    3 -> 0[label="a,b"];
  }

2.

Par un automate déterministe ! car l’automate précédent a, pour $n=3$, $6<8$ états et reconnaît bien

\[𝛴^\ast a 𝛴^{n-1}\]

---

On construit une injection de $𝛴^{n-1}$ dans l’ensemble des états $Q$.

\[𝜑 ≝ \begin{cases} 𝛴^{n-1} ⟶ Q \\ w \mapsto 𝛿(q_0, w) \end{cases}\]

Montrons que $𝜑$ est injective :

• Si, par l’absurde : $w≠w’$ et

\[𝛿(q_0, w) = 𝛿(q_0, w')\]

alors il on note $i$ ($1≤ i ≤n$) un indice tel que

\[a = w_i ≠ w'_i = b\]

(sans perte de généralité)

Donc comme l’automate est déterministe :

• $𝛿(q_0, w a^i) ∈ F$ car $a$ est en $n$-ième position avant la fin dans $wa^i$
• $𝛿(q_0, w’ a^i) ∉ F$ car $b$ est en $n$-ième position avant la fin dans $w’ a^i$

: c’est absurde.

Donc \(2^{n-1} = \vert 𝛴^n \vert ≤ \vert Q \vert\)

3.

$2^n$ majore clairement le nombre d’états de l’automate déterminisé, en construisant l’automate des parties.

Et dans certains cas (cf. question précédente), tout DFA reconnaissant $L$ a au moins $2^{n-1}$ états.

EX 2

1.

Principe des tiroirs.

2.

Car sinon : Soit $N$ le nombre d’états de l’automate.

On applique la deuxième version du lemme de l’étoile à $a^{N-1} b^{N-1}$ : il existe $k≥1$ tel que les mots $a^{N-1} (b^{k})^\ast b^{N-1-k}$ sont reconnus, ce qui est absurde.

3.

a).

Soit

\[u∈L_{\#} ≝ (\#^{+}L)∪𝛴^\ast\]

• Si $u∈𝛴^\ast$ : Ok

• Sinon : \(u∈\#^+L\)

  Avec $N=1$ :

  \[u_1=𝜀, u_2 = \#, u_3 = v\]

  alors \(u_1 u_2^\ast u_3 ⊆ L_{\#}\)

b)

Contraposée : Si \(L_{\#}\) est reconnaissable, montrons que $L$ est rationnel.

On sait que \(\#^+L\) est rationnel, par hypothèse.

Soit $𝜇$ un morphisme tel que :

\[\begin{cases} 𝜇(\#)=𝜀 \\ ∀a≠\#, 𝜇(a)=a \end{cases}\]

Alors

\[L = 𝜇(\#^+L)\]

et $L$ est donc rationnel.

c).

Si \(L_{\#}\) satisfait la seconde version du lemme :

$w∈L$, avec $w = v_1 v_2 v_3$, où

\[\#w = \#v_1 v_2 v_3 ∈ L_{\#}\]

Si $\vert v_2 \vert≥ N$,

\[∃ (u_1, u_2, u_3); \# v_1 u_1 (u_2)^\ast u_3 v_3 ⊆ L_{\#} ∩ \#^\ast L\] \[v_1 u_1 (u_2)^\ast u_3 v_3 ⊆ L\]

4.

a).

$L_{$}$ satisfait la seconde version :

Pour $n=3$ :

$w= v_1 v_2 v_3 ∈ L$ avec $\vert v_2 \vert≥3$

• Si \(\$∈v_2\) :

  \[v_2 = u_1 \underbrace{\$}_{u_2} u_3 \\ v_1 u_1 \$^\ast u_3 v_3 ⊆ L\]

• Si \(\$\not∈v_2\) :

  \[v_2 ∈L_2 \\ v_2= u_1 \underbrace{a}_{∈𝛴} u_3 \\ v_1 u_1 a^\ast u_3 v_3 ⊆ L_2 ⊆ L\]

b).

Supposons \(L_{\#}\) régulier.

Alors

\[L_1 = \underbrace{L_{\#}}_{\text{régulier}} ∩ \underbrace{(\$^+ 𝛴)^\ast \$^+}_{\text{régulier}}\]

est régulier.

Soit $𝜇$ le morphisme qui envoie $a∈𝛴$ sur $a$, \(\$\) sur $𝜀$, alors

\[L = 𝜇(L_1)\]

est régulier

c).

Supposons que \(L_{\#}\) satisfait 3) pour un certain $n$.

Soit

\[w = u_0 u_1 ⋯ u_n u_{n+1} ∈L\]

avec $u_i≠𝜀$ pour $1≤i≤n$

Pour $u = a_1 ⋯ a_k$,

\(\overline{u} = \$ a_1 \$ ⋯ \$ a_k \\)$

\[\overline{u_0} \overline{u_1} ⋯ \overline{u_{n+1}}∈L_1 ⊆ L_{\#}\] \[∃j<k, \overline{u_0} \overline{u_1} ⋯ \overline{u_j} (\overline{u_{j+1}} ⋯ \overline{u_k})^\ast \overline{u_{k+1}} ⋯ \overline{u_{n+1}}⊆ L_{\#}\]

donc $⊆L_1$

Donc

\[u_0 u_1 ⋯ u_j (u_{j+1} ⋯ u_k)^\ast u_{k+1} ⋯ u_n u_{n+1}⊆L\]