TD 1 : Introduction

Chargée de TD : Marie FORTIN

EX 1

1.

$𝒜_{1}$ :

L (𝒜_{1}) = (a + b)^{*} a b a

DFA :

L (𝒜_{2}) = (a + b)^{*} a (a + b)^{2}

DFA :

2.

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

𝛴^{*} 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 \neq w^{'}$ et

𝛿 (q_{0}, w) = 𝛿 (q_{0}, w^{'})

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

a = w_{i} \neq w_{i}^{'} = b

(sans perte de généralité)

Donc comme l’automate est déterministe :

$𝛿 (q_{0}, w a^{i}) \in F$ car $a$ est en $n$ -ième position avant la fin dans $w a^{i}$
$𝛿 (q_{0}, w^{'} a^{i}) \notin F$ car $b$ est en $n$ -ième position avant la fin dans $w^{'} a^{i}$

: c’est absurde.

Donc $2^{n - 1} = | 𝛴^{n} | \leq | Q |$

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 \geq 1$ tel que les mots $a^{N - 1} (b^{k})^{*} b^{N - 1 - k}$ sont reconnus, ce qui est absurde.

3.

a).

Soit

u \in L_{#} ≝ (#^{+} L) \cup 𝛴^{*}

Si $u \in 𝛴^{*}$ : Ok
Sinon : $u \in #^{+} L$

Avec $N = 1$ :
$u_{1} = 𝜀, u_{2} = #, u_{3} = v$
alors $u_{1} u_{2}^{*} u_{3} \subseteq 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} 𝜇 (#) = 𝜀 \\ \forall a \neq #, 𝜇 (a) = a \end{cases}

Alors

L = 𝜇 (#^{+} L)

et $L$ est donc rationnel.

c).

Si $L_{#}$ satisfait la seconde version du lemme :

$w \in L$ , avec $w = v_{1} v_{2} v_{3}$ , où

# w = # v_{1} v_{2} v_{3} \in L_{#}

Si $| v_{2} | \geq N$ ,

\exists (u_{1}, u_{2}, u_{3}); # v_{1} u_{1} (u_{2})^{*} u_{3} v_{3} \subseteq L_{#} \cap #^{*} L

v_{1} u_{1} (u_{2})^{*} u_{3} v_{3} \subseteq L

4.

a).

$L_{$}$ satisfait la seconde version :

Pour $n = 3$ :

$w = v_{1} v_{2} v_{3} \in L$ avec $| v_{2} | \geq 3$

Si $$ \in v_{2}$ :
$\begin{matrix} v_{2} = u_{1} \underset{u_{2}}{\underset{⏟}{$}} u_{3} \\ v_{1} u_{1} $^{*} u_{3} v_{3} \subseteq L \end{matrix}$
Si $$ \notin v_{2}$ :
$\begin{matrix} v_{2} \in L_{2} \\ v_{2} = u_{1} \underset{\in 𝛴}{\underset{⏟}{a}} u_{3} \\ v_{1} u_{1} a^{*} u_{3} v_{3} \subseteq L_{2} \subseteq L \end{matrix}$

b).

Supposons $L_{#}$ régulier.

Alors

L_{1} = \underset{régulier}{\underset{⏟}{L_{#}}} \cap \underset{régulier}{\underset{⏟}{($^{+} 𝛴)^{*} $^{+}}}

est régulier.

Soit $𝜇$ le morphisme qui envoie $a \in 𝛴$ 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} \dots u_{n} u_{n + 1} \in L

avec $u_{i} \neq 𝜀$ pour $1 \leq i \leq n$

Pour $u = a_{1} \dots a_{k}$ ,

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

\overset{―}{u_{0}} \overset{―}{u_{1}} \dots \overset{―}{u_{n + 1}} \in L_{1} \subseteq L_{#}

\exists j < k, \overset{―}{u_{0}} \overset{―}{u_{1}} \dots \overset{―}{u_{j}} (\overset{―}{u_{j + 1}} \dots \overset{―}{u_{k}})^{*} \overset{―}{u_{k + 1}} \dots \overset{―}{u_{n + 1}} \subseteq L_{#}

donc $\subseteq L_{1}$

Donc

u_{0} u_{1} \dots u_{j} (u_{j + 1} \dots u_{k})^{*} u_{k + 1} \dots u_{n} u_{n + 1} \subseteq L

Share on

Twitter Facebook Google+ LinkedIn

EX 1

1.

2.

3.

EX 2

1.

2.

3.

a).

b)

c).

4.

a).

b).

c).

Share on

Leave a comment