Grammaire

def.: Soit G = (V, Σ, R, S) tel que

- V est un alphabet,

- Σ ⊆ V est l’ensemble des symboles terminaux (V −Σ est l’ensemble des symboles non terminaux),

- R ⊆ (V^{+} × V^{∗}) est un ensemble fini de règles ((u, v) est noté u → v),

- S ∈ V − Σ le symbole de départ.

G est une grammaire.

exe. V = \begin{aligned}\{ & P hrase, Sujet, V erbe, P ronom, \\ & il, elle, dort, écoute\}, \end{aligned}

Σ = {il, elle, dort, écoute},

R = \begin{aligned}\{ & P hrase → Sujet V erbe & Sujet → P ronom \\ & P ronom → il & P ronom → elle \\ & V erbe → dort & V erbe → écoute\}, \end{aligned}

S = P hrase

G_{f} = (V, Σ, R, S) est une grammaire.

Grammaires (suite)

def.: Soit une grammaire G = (V, Σ, R, S) et u ∈ V^{+} , v ∈ V^{∗}. La grammaire G permet de dériver v de u en une étape (u ⇒ v) si

- u = xu′y,

- v = xv′y et

- u′ → v′

exe.:Sujet V erbe P ronom ⇒ Sujet dort P ronom en effet en posant x = Sujet, y = P ronom, u′ = V erbe et v′ = dort, nous avons V erbe → dort ∈ R.

def. Soit une grammaire G = (V, Σ, R, S) et u ∈ V^{+} , v ∈ V^{∗}. La grammaire G permet de dériver v de u en plusieurs étapes (u ⇒^{∗} v) si ∃k ≥ 0 et v_{0}, …, v_{k} ∈ V^{+} tels que

- u = v_{0},

- v = v_{k} et

- v_{i} ⇒ v_{i+1} , 0 ≤ i < k.

Grammaire (suite)

exe.: P ronom dort elle est dérivable de Sujet V erbe Sujet par la grammaire G_{f}

(Sujet V erbe Sujet ⇒^{∗} P ronom dort elle)

règles

Sujet V erbe Sujet  Sujet → P ronom
Sujet V erbe P ronom V erbe → dort
Sujet dort P ronom  Sujet → P ronom
P ronom dort P ronom P ronom → elle

P ronom dort elle def. Un mot v ∈ Σ^{∗} est généré par une grammaire G si S ⇒^{∗} v. exe. Le mot elle dort est généré par la grammaire G_{f} :

règles

P hrase  P hrase → Sujet V erbe
Sujet V erbe V erbe → dort
Sujet dort Sujet → elle

elle dort

Grammaire (suite)

def. Le langage généré par une grammaire G L(G) = {v ∈ Σ^{∗} tel que S ⇒^{∗} v}. exe. L(G_{f}) = {il dort, il écoute, elle dort, elle écoute}. exo. Soit la grammaire

G = \begin{matrix}(\{S, a, b, A, B\}, \{a, b\}, \\ \{S → ε, S → aB, \\ S → bA, A → aS, \\ A → bAA, B → bS, \\ B → aBB\}, S). \end{matrix}

Démontrez que L(G) est l’ensemble des mots comportant le meme nombre de lettres a et de lettres b.

Typologie des grammaires

4 types de grammaires :

- type 0 : grammaires générales,

- type 1 : grammaires sensibles au contexte,

- type 2 : grammaires hors contexte,

- type 3 : grammaires régulières.

Th.: type 3 ⊂ type 2 ⊂ type 1 ⊂ type 0.

def.: Une grammaire est régulière si toute production est de la forme A → wB ou A → w avec A, B ∈ V − Σ et w ∈ Σ^{∗}.