Exercice 1
==========

On a vue en cours que le langage `PAIR` peut être défini par :

* Définition 1:
	* **base** : $2 \in PAIR$
	* **règle** : si $x \in PAIR$, alors $x+2 \in PAIR$
* Définition 2:
	* **base** : $2 \in PAIR$
	* **règle** : si $(x,y)\ \in PAIR^2$, alors $x+y \in PAIR$

### Question 1

> Vérifier que `16` est dans `PAIR`


##### En utilisant la *Définition 1*

* $2 \in PAIR \rightarrow 2+2 = 4 \in PAIR$
* $4 \in PAIR \rightarrow 4+2 = 6 \in PAIR$
* $6 \in PAIR \rightarrow 6+2 = 8 \in PAIR$
* $8 \in PAIR \rightarrow 8+2 = 10 \in PAIR$
* $10 \in PAIR \rightarrow 10+2 = 12 \in PAIR$
* $12 \in PAIR \rightarrow 12+2 = 14 \in PAIR$
* $14 \in PAIR \rightarrow 14+2 = 16 \in PAIR$


##### En utilisant la *Définition 2*

* $2 \in PAIR \rightarrow 2+2 = 4 \in PAIR$
* $8 \in PAIR \rightarrow 4+4 = 8 \in PAIR$
* $8 \in PAIR \rightarrow 8+8 = 16 \in PAIR$







Exercice 2
==========

Soit $\Sigma=\{a, b, c\}$ et soit deux mots : $\omega = ababc$ et $q=caba$


### Question 1

> 1. Calculer $\omega^0$
> 2. $\omega^1$
> 3. $\omega^2$


> 1. $\omega^0 = \epsilon$
> 2. $\omega^1 = \omega = ababc$
> 3. $\omega^2 = \omega \omega = ababcababc$


### Question 2

> Calculer $\omega q^2 \omega$

> $\omega q^2 \omega = \omega qq \omega = ababccabacabaababc$


### Question 3

> 1. Calculer $|\omega|_{ab}$
> 2. Calculer $|(ab)^4|$
> 3. Calculer $|(ab)^4|_{aba}$


> 1. $|\omega|_{ab} = 2$
> 2. $|(ab)^4| = 4$
> 3. $|(ab)^4|_{aba} = 3$


### Question 4

> Donner pour q :
>
> 1. les préfixes
> 2. les préfixes propres
> 3. les suffixes
> 4. les suffixes propres

> On a :
>
> 1. préfixes de q = $\{\epsilon,c,ca,cab,caba\}$
> 2. préfixes propres de q = $\{\epsilon,c,ca,cab\}$
> 3. suffixes de q = $\{caba,aba,ba,a,\epsilon\}$
> 4. suffixes propres de q = $\{aba,ba,a,\epsilon\}$


Exercice 3
==========

### Question 1

> Quels sont les 2 langages dont la fermeture en étoile donne le langage uniquement composé du mot vide $\epsilon$ ?

> 1. $\{\epsilon\}$
> 2. $\{\}$


### Question 2

> Les mots suivants sont-ils générés par le langage $(ab^*)b^*$ :


> * $\epsilon \rightarrow a\epsilon\epsilon \rightarrow$ `FALSE`
> * $a \rightarrow a\epsilon\epsilon \rightarrow$ `TRUE`
> * $aa \rightarrow ab\epsilon \rightarrow$ `FALSE`
> * $ba \rightarrow ab\epsilon \rightarrow$ `FALSE`
> * $abbb \rightarrow ab^4 \epsilon = a\epsilon b^4 = ab^2b^2 = ... \rightarrow$ `TRUE`
> * $ababb \rightarrow ab^1 ... \rightarrow$ `FALSE`
> * $baba \rightarrow$ `FALSE`