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

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

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

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

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

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.

Le même type de jeu de règles peut être établi pour une grammaire régulière à gauche.

Liens utiles

Cours sur les grammaires régulières (avec introduction sur les grammaires en général).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.