Julien Marcil - julien.marcil@ift.ulaval.ca
Définition: Un langage est dit régulier s’il existe un automate fini déterministe qui le reconnaît.
Une façon de montrer qu’un langage est régulier est de construire un automate qui reconnaît ce langage.
Si $L$ est un langage régulier, alors il existe un entier $p \ge 1$ (appelé longueur de pompage) tel que pour tout mot $w \in L$ avec $\lvert w \rvert \ge p$, il existe des mots $x,y,z$ tels que $w = xyz$ et
Pour prouver qu’un langage est non régulier, on fait une preuve par contradiction.
Soit $\Sigma = \{0,1\}$. Prouver que le langage $L=\{w \mid w \text{ contient le même nombre de 0 et de 1} \}$ n'est pas régulier.
Définition: Un langage est dit hors contexte (ou non contextuelle) s’il existe une grammaire hors contexte qui le génère.
Si $L$ est un langage hors contexte, alors il existe un entier $p \ge 1$ (appelé longueur de pompage) tel que pour tout mot $w \in L$ avec $\lvert w \rvert \ge p$, il existe des mots $u,v,x,y,z$ tels que $w = uvxyz$ et
Pour prouver qu’un langage est non hors contexte, on fait une preuve par contradiction.
Soit $\Sigma = \{a,b,c\}$. Prouver que le langage $L=\{w \mid w \text{ contient le même nombre de } $a$, $b$ \text{ et } $c$ \}$ n'est pas régulier.
Une machine de turing peut:
Définition: Un langage $L$ est dit Turing-acceptable (ou récursivement énumérable)s’il existe une machine de Turing qui accepte les mots de $L$.
Étant donnée une entrée $w$
Définition: Un langage $L$ est dit Turing-décidable (ou décidable)s’il existe une machine de Turing $M$ qui accepte les mots de $L$ et rejette les autres mots.
Étant donnée une entrée $w$
Soit un le langage $L$. Si $L$ est Turing-décidable, alors $\overline{L}$ est Turing-décidable.
Soit un le langage $L$. Si $L$ et $\overline{L}$ sont Turing-acceptable, alors $L$ est Turing-décidable.
Les règles formelles de calcul (machines de Turing, le λ-calcul, les fonctions récursives...) formalisent correctement la notion d'algorithme.
Un langage informatique est dit Turing-complet s'il permet de représenter toutes les fonctions calculables au sens de Turing et Church.
Dans un tel langage, il est possible de programmer n'importe quelle machine de Turing, mais également tout ce que l'on peut programmer dans une machine de Turing.
Un language $L$ se réduit au language $K$, noté $L \le_m K$ si il existe $f: \Sigma^* \to \Sigma^*$ une fonction calculable tel que
$$\forall_{w \in \Sigma^*} \quad w \in L \ \Leftrightarrow \ f(w) \in K$$
Si $A \le_m B$ et $B$ est décidable, alors $A$ est décidable.
Si $A \le_m B$ et $A$ n'est pas décidable, alors $B$ n'est pas décidable.
$$E_{\text{AFD}} = \{\langle B \rangle \mid B \text{ est un AFD et } L(B) = \emptyset\}$$
$E_{\text{AFD}}$ est un langage décidable.
$$EQ_{\text{AFD}} = \{\langle A, B \rangle \mid A \text{ et } B \text{ sont des AFD et } L(A) = L(B) \}$$
$EQ_{\text{AFD}}$ est un langage décidable.
Soit $C$ un $\text{AFD}$ tel que $$L(C) = \big( L(A) \cap \overline{L(B)} \big) \cup \big( \overline{L(A)} \cap L(B) \big)$$
$$L(A) = L(B) \ \Leftrightarrow \ L(C) = \emptyset$$
$$A_{\text{MT}} = \{\langle M, w\rangle \mid M \text{ est une MT qui accepte } w\}$$
$\text{MT}$: machine de Turing
$A_{\text{TM}}$ est un langage Turing-acceptable.
$A_{\text{TM}}$ n'est pas un langage décidable.
$\overline{A_{\text{TM}}}$ n'est pas un langage Turing-acceptable.
$$HALT_{\text{MT}} = \{\langle M, w \rangle \mid M \text{ est une MT et } M \text{ s'arrête sur } w \}$$
$HALT_{\text{MT}}$ n'est pas un langage décidable.
$\rrmacro{PLUS}{r_1, r_2} = r_1 + r_2$
$ \rrset{r_0}{r_1} \\ \rrrep{r_2}[ \\ \quad \rrinc{r_0} \\ ] $
$\rrmacro{MULT}{r_1, r_2} = r_1 \times r_2$
$ \rrrep{r_1}[ \\ \quad \rrrep{r_2}[ \\ \quad\quad \rrinc{r_0} \\ \quad ] \\ ] $
$\rrmacro{EXP}{r_1, r_2} = r_1^{r_2}$
$ \rrset{r_0}{1} \\ \rrrep{r_2}[ \\ \quad \rrinvoke{r_0}{MULT}{r_0,r_1} \\ ] $
La classe de complexité $\mathsf{P}$ est définie comme
$$ \bigcup_{k \ge 0} \mathsf{TIME}(n^k) $$
La classe P correspond aux langages décidables en pratique en un temps raisonnable.
Définition: Un vérificateur polynômial pour un langage $L$ est une machine de Turing $V$ tel que pour tout $w \in \Sigma^*$:
le temps de calcul de $V$ sur $\langle w, c \rangle$ est polynômial en la taille de $w$.
Un $c$ tel que $\langle w, c \rangle \in L(V)$ est appelé certificat ou preuve ou temoin de l’appartenance de $w$ au langage $L$.
La classe de complexité $\mathsf{NP}$ est l’ensemble des langages qui possèdent un vérificateur polynômial.
Un language $L$ se réduit au language $K$, noté $L \le_p K$ si il existe $f: \Sigma^* \to \Sigma^*$ une fonction calculable en temps polynômiales tel que
$$\forall_{w \in \Sigma^*} \quad w \in L \ \Leftrightarrow \ f(w) \in K$$
Définition: Le langage $L$ est NP-difficile si pour tout $L' \in \mathsf{NP}$ on a $$ L' \le_p L $$
un langage NP-difficile est aussi difficile à décider, ou plus difficile, que n’importe quel langage de NP.
Définition: Le langage $L$ est NP-complet si
Si $L$ est un langage NP-complet et $L \in \mathsf{P}$, alors
$$\mathsf{P} = \mathsf{NP}$$
Si l’on peut résoudre un seul problème NP-complet efficacement, alors on aura résolu efficacement tous les problèmes de NP.