Langage régulier

def.: L’ensemble R des langages réguliers (ou rationnels) sur un alphabet Σ est le plus petit ensemble satisfaisant :

- ∅ ∈ R, {ε} ∈ R

- {a} ∈ R, ∀a ∈ Σ

- si A, B ∈ R alors A ∪ B, A · B, A^{∗} ∈ R.

exe.: Les langages {a}^{∗} · ({a} ∪ {b}^{∗})({b}^{∗})^{∗} et {a}^{∗} · {b}^{∗} sont des langages réguliers (égaux !).

def.: Les expressions régulières pour un alphabet Σ sont les expressions formées par les règles suivantes :

- ∅, ε et tous les éléments de Σ sont des expressions régulières.

- si α et β sont des expressions régulières alors (αβ), (α + β), et (α)^{∗} sont des expressions régulières.

exe.: Les expressions a^{∗}(a + b^{∗})(b^{∗})^{∗} et a^{∗}b^{∗} sont des expressions régulières.

Langage régulier (suite)

def.: Le langage L(ξ) représenté par l’expression régulière ξ est défini par :

- L(∅) = ∅, L(ε) = {ε},

- L(a) = {a}, ∀a ∈ Σ,

- L(α + β) = L(α) ∪ L(β),

- L(αβ) = L(α) · L(β),

- L(α^{∗}) = L(α)^{∗}.

Th.: Un langage est régulier si et seulement si il est dénoté par une expression régulière.

exe.: L’expression régulière a^{∗}(a + b^{∗})(b^{∗})^{∗} dénote le langage régulier {a}^{∗} · ({a} ∪ {b}^{∗})({b}^{∗})^{∗}.

Th.: L’ensemble des langages réguliers est dénombrable