Théorème du gonflement et langages non

réguliers

Th.: Soit L un langage régulier infini. Alors ∃u, v, w ∈ Σ^{∗}, v ≠ ε tels que ∀n ≥ 0, uv^{n}w ∈ L.

Pr. Inf. Soit M = (Q, Σ, δ, s, F) avec | Q |= m et x ∈ L(M) tel |x|> m. Alors ∃q ∈ Q, uvw ∈ Σ^{∗} et f ∈ F tels que x = uvw et (s, x) ⊢_{M}^{∗} (q, vw) ⊢_{M}^{∗} (q, w) ⊢_{M}^{∗} (f, ε) donc uv^{∗}w ∈ L(M).

Th.: Soit L un langage régulier infini et soit x ∈ L tel que |x|≥|Q|, Q ensemble des états d’un automate non déterministe acceptant L. Alors ∃u, v, w ∈ Σ^{∗}, v ≠ ε, |uv|≤|Q| tels que uvw = x et ∀n ≥ 0, uv^{n}w ∈ L.

Exemple : Le langage L = a^{n^{2}} n’est pas régulier.

Exemple : Le langage L = {a^{n} | n premier} n’est pas régulier.

Exemple : Le langage L = a^{n}b^{n} n’est pas régulier.