Grammaires
En introduisant des critères plus ou moins restrictifs sur la forme des règles de grammaire, on obtient des classes de grammaires hiérarchisées (des types de grammaires), ordonnées par inclusion. La classification des grammaires, définie en 1957 par Noam Chomsky, distingue quatre classes.
Classification de Chomsky
Type 0 : pas de restriction sur les règles.
Type 1 : grammaires sensibles au contexte ou contextuelles. Les règles de R sont de la forme :
- uAv → uwv avec A ∈ N, u, v ∈ (N ∪ T)∗ et w ∈ (N ∪ T)+
- Autrement dit, le symbole non terminal A est remplacé par w si on a les contextes u à gauche et v à droite.
Type 2 : grammaires hors-contexte. Les règles de R sont de la forme :
- A → w avec A ∈ N et w ∈ (N ∪ T)∗
- Autrement dit, le membre de gauche de chaque règle est constitué d’un seul symbole non terminal.
Type 3 : grammaires régulières
- à droite. Les règles de R sont de la forme
A → aB ou A → a avec A, B ∈ N et a ∈ T - à gauche. Les règles de R sont de la forme
A → Ba ou A → a avec A, B ∈ N et a ∈ T - Autrement dit, le membre de gauche de chaque règle est constitué d’un seul symbole non terminal, et le membre de droite est constitué d’un symbole terminal et éventuellement d’un symbole non terminal. Pour les grammaires régulières à droite, le symbole non terminal doit toujours se trouver à droite du symbole terminal tandis que pour les grammaires régulières à gauche il doit se trouver à gauche.
Exemple 1
On considère le langage L des mots sur {0, 1} qui représentent des entiers pairs non signés en base 2 (les mots de ce langage se terminent tous par 0 et ne commencent pas par 0, sauf pour l’entier nul). Définir formellement L et construire une grammaire régulière décrivant L.
Le langage est de la forme suivante : L = {0, 1u0/ u ∈ {0, 1}∗}
On définit la grammaire régulière à droite G = (T, N, S, R) où
T = { 0, 1 }
N = { S, U }
R = { S → 0 | 1U
U → 1U | 0U | 0 }
ainsi que la grammaire régulière à gauche G = (T, N, S, R) où
T = { 0, 1}
N = { S, U }
R = { S → 0 | U0
U → U1 | U0 | 1 }
De préférence, on prendre toujours la grammaire régulière à droite pour l’étude des états futurs dans les automates.
Exemple 2
Voici les productions de grammaire : P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → ε. Les non-terminaux de la grammaire sont {P,Q,R}, le symbole initial est P.
En dénotant avec Xp, Xq, Xr les langages acceptés à partir des états P, Q et R respectivement, le système d’équations pour ces langages est :
FR 
EN 
ES