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

Leave a Comment