Grammaire régulière

En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier.

Définition[modifier | modifier le code]

Une grammaire régulière peut être « à gauche » ou « à droite ».

Une grammaire régulière à gauche est un ensemble de règles de la forme :

X\rightarrow Ya

X\rightarrow a

X\rightarrow \epsilon

où $X$ , $Y$ sont des symboles non-terminaux et $a$ un symbole terminal.

Une grammaire régulière à droite est un ensemble de règles de la forme :

X\rightarrow aY

X\rightarrow a

X\rightarrow \epsilon

où $X$ , $Y$ sont des symboles non-terminaux et $a$ un symbole terminal. De plus, comme pour toutes grammaires, on considère un non-terminal particulier appelé axiome et noté $S$ .

Exemple[modifier | modifier le code]

La grammaire suivante est une grammaire régulière à droite :

S\rightarrow dA\mid rB\mid mC\mid \epsilon

A\rightarrow oS

B\rightarrow eS

C\rightarrow iS

Avec la grammaire précédente, on peut engendrer le mot $dodomi$ . En effet : $S\rightarrow dA\rightarrow doS\rightarrow dodA\rightarrow dodoS\rightarrow dodomC\rightarrow dodomiS\rightarrow dodomi$ .

Équivalence entre automates finis et grammaires régulières[modifier | modifier le code]

On peut transformer de manière effective une grammaire régulière à droite en automate fini déterministe et vice versa. Les non-terminaux correspondent aux états de l'automate.

Exemple[modifier | modifier le code]

Considérons la grammaire ci-dessus. L'automate correspondant est le suivant :

La suite de dérivations $S\rightarrow dA\rightarrow doS\rightarrow dodA\rightarrow dodoS\rightarrow dodomC\rightarrow dodomiS\rightarrow dodomi$ correspond à la lecture du mot $dodomi$ dans l'automate où on passe successivement dans les états : S, A, S, A, S, C, S.

Définition formelle[modifier | modifier le code]

Soit une grammaire régulière à droite $G=\{N,\Sigma ,P,S\}$ , alors l'automate $A=\{Q,\Sigma ',\delta ,Q_{0},Q_{T}\}$ équivalent à G est défini tel que:

$Q=N\cup \{q_{t}\}$ avec $Q$ l'ensemble des états et $q_{t}$ un état puits terminal,
$\Sigma '=\Sigma$ avec $\Sigma '$ l'ensemble des symboles terminaux
$Q_{0}=S$ avec $Q_{0}$ l'état initial
$\delta \in Q\times \Sigma \rightarrow Q$ est la fonction de transition telle que, à la lecture d'un terminal $x$ à partir d'un état $q_{i}$ vers un autre état $q_{f}=\delta (q_{i},x)$ .

La lecture de $P$ permet de construire $\delta$ . Pour chaque $Pi\in P$ :

Si $P_{i}=X\rightarrow aY$ alors on a $\delta (X,a)=Y$
Si $P_{i}=X\rightarrow a$ alors on a $\delta (X,a)=q_{t}$
Si $P_{i}=X\rightarrow \epsilon$ alors on a $X\in Q_{T}$ , $Q_{T}$ L'ensemble des états terminaux.