Eléments d’ informatique théorique Série 13

Définition 1 La classe T des langages dits “tally” est définie comme

T = {L | L ⊆ Σ^{∗} ∩ {0}^{∗}}

La classe S des langages dits “sparse” est définie comme

S = {L | L ⊆ Σ^{∗}et ∃c∀n|{w | w ∈ L ∩ Σ^{n}}| ≤ n^{c}}

La densité d’un langage L est définie par la fonction

d(n) = \frac{nombre de mots de longueur n de L}{nombre de mots de longueur n de Σ^{∗}}

Exercice 13.1 En considérant Σ = {0, 1}:

1. quelle est la densité d’un langage appartenant à T ?

2. quelle est la densité d’un langage appartenant à S ?

3. prouvez que T ⊆ S!

Définition 2 Class complémentaire Pour une classe de langages C, la classe associée co-C est définie comme

co-C = \{L | \overline{L} ∈ C\}

Exercice 13.2 Prouvez que co-DTIME(f(n)) = DTIME(f(n)) Exercice 13.3 Prouvez que DSPACE(2^{2^{n}+n}) inclut strictement DSPACE(2^{2^{n}}) !

Que peut-on dire de DTIME(2^{2^{n}+n}) et DTIME(2^{2^{n}}) ? Exercice 13.4 Etablissez la relation entre les deux classes de complexité:

1. DSPACE(n^{2}) et DSPACE(f(n)) où f(n) = \begin{cases}n^{3} & si n est pair, \\ n & sinon. \end{cases}

2. DTIME(2^{n}) et DSPACE(5^{n}).