Aspects Algébriques

Lemme de pompage

Rappel : Soit ${\cal L}$ rationnel. $\exists\,n$ tel que : si $z\in {\cal L}$ et $\vert z\vert\geq n$, alors z=uvw avec $\vert uv\vert\leq n$ et $\vert v\vert\geq 1$ et $\forall i\geq 0,uv^iw\in {\cal L}$.

1.

Montrer à l'aide du lemme de pompage que le langage suivant n'est pas rationnel :

$$\{a^nb^n,n\geq 0\}$$

2.

Montrer à l'aide du lemme de pompage que le langage suivant n'est pas rationnel :

$$\{a^{i^3},i\geq 0\}$$