Caractérisation des langages réguliers

Th.: Un langage est régulier ssi il est accepté par un automate fini ssi il est généré par une grammaire régulière.

Expression régulière : descriptif, Automate fini : analytique, Grammaire régulière : génératif.

Langage régulier ⇒ automate fini

Const.: Construisons par induction un AFND M_{ξ} à partir d’une expression régulière ξ (M_{i} = (Q_{i}, Σ_{i}, Δ_{i}, s_{i}, F_{i}) automate pour l’expression régulière α_{i}) :

- si ξ = ∅ alors M_{ξ} = ({q}, ∅, ∅, q, ∅)

- si ξ = ε alors M_{ξ} = ({q}, ∅, ∅, q, {q})

- si ξ = σ ∈ Σ alors M_{ξ} = ({q_{0}, q_{1}}, {σ}, {(q_{0}, σ, q_{1})}, q_{0}, {q_{1}})

- si ξ = α_{1}α_{2} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ Q_{2}, Σ_{1} ∪ Σ_{2}, \\ Δ_{1} ∪ Δ_{2} ∪ \{(q, ε, s_{2})/q ∈ F_{1}\}, s_{1}, F_{2}) \end{matrix}

- si ξ = α_{1}^{∗} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ \{s\}, Σ_{1}, Δ_{1} ∪ \{(q, ε, s_{1})/q ∈ F_{1}\}, \\ s, F_{2} ∪ \{s\}) \end{matrix}

- si ξ = α_{1} + α_{2} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ Q_{2} ∪ \{s\}, Σ_{1} ∪ Σ_{2}, \\ Δ_{1} ∪ Δ_{2} ∪ \{(s, ε, s_{1}), (s, ε, s_{2})\}, s, F_{1} ∪ F_{2}) \end{matrix}

Automate fini ⇒ Grammaire régulière

Const.: Construisons une grammaire régulière G = (V_{G}, Σ_{G}, S_{G}, R_{G}) à partir d’un AFND M = (Q, Σ, Δ, s, F) telle que L(G) = L(M) comme suit :

- V_{G} = Q ∪ Σ

- Σ_{G} = Σ

- S_{G} = s

- R_{G} = \begin{matrix}\{A → wB/(A, w, B) ∈ Δ\}∪ \\ \{A → ε/A ∈ F \} \end{matrix}

Grammaire régulière ⇒ Automate fini

Const.: Construisons un AFND M = (Q, Σ, Δ, s, F) à partir d’une grammaire régulière G = (V_{G}, Σ_{G}, S_{G}, R_{G}) tel que L(M) = L(G) comme suit :

- Q = (V_{G} − Σ_{G}) ∪ {f}, (f ∉ V_{G}),

- Σ = Σ_{G},

- s = S_{G},

- F = {f},

- Δ = \begin{matrix}\{(A, w, B)/A → wB ∈ R_{G}\}∪ \\ \{(A, w, f)/A → w ∈ R_{G}\} \end{matrix}