Grammaire rationnelle


Grammaire rationnelle

Grammaire régulière

Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d'un langage régulier, en particulier dans le domaine des langages de programmation, il ne s'en trouve pas moins que, techniquement, la reconnaissance d'un mot d'un langage régulier s'effectue par la traduction d'expressions rationnelles en grammaire régulière.

Sommaire

Notation

Une grammaire régulière se note de la même manière qu'une grammaire hors-contexte:

G = {N,Σ,P,S}
N est le vocabulaire non terminal, Σ est le vocabulaire terminal, P est l'ensemble des règles de production et S \in N est le non terminal initial.

Définition

L'ensemble des grammaires régulières est inclus dans l'ensemble des grammaires hors-contexte. Aussi les règles de production ne doivent comporter aucun symbole terminal dans leur partie gauche.

De plus, les règles de production doivent être de l'une des 2 formes suivantes:

  • grammaire régulière à droite
 X \rightarrow Ya
 X \rightarrow a
 X \rightarrow \epsilon
  • grammaire régulière à gauche
 X \rightarrow aY
 X \rightarrow a
 X \rightarrow \epsilon
X,Y \in N,  a \in \Sigma et ε est le mot vide.

A la vue des règles de production, on peut en déduire que le principe d'une grammaire régulière est de reconnaitre un mot en partant d'une de ses extrémités et de progresser vers l'autre bout du mot en reconnaissant un seul caractère à la fois.

Mise en œuvre

Puisqu'une grammaire dite régulière est également hors-contexte, il est possible de mettre en œuvre une grammaire régulière par le biais d'un automate à pile. Il est cependant plus à propos d'utiliser un automate fini déterministe. La traduction d'une grammaire régulière en un automate est aisée, voire mécanique.

Soit une grammaire régulière à gauche G = {N,Σ,P,S}, alors l'automate A = {Q,Σ',δ,Q0,QT} équivalent à G est défini tel que:

  • Q = N \cup \{ q_t \} avec Q l' ensemble des états et qt un état puit terminal,
  • Σ' = Σ avec Σ' l'ensemble des symboles terminaux
  • Q0 = S avec Q0 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 qi vers un autre état qf = δ(qi,t).
La lecture de P permet de construire δ. Pour chaque Pi \in P:
  • Si P_i = X \rightarrow aY alors on a δ(X,a) = Y
  • Si P_i = X \rightarrow a alors on a δ(X,a) = qt
  • Si P_i = X \rightarrow \epsilon alors on a X \in Q_T, QT L'ensemble des états terminaux.

On applique enfin les algorithmes de déterminisation et de minimisation afin d'obtenir un automate déterministe et minimal.

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

Exemple de conversion

Soit la grammaire G = {N,Σ,P,S} dont les règles de production sont:

S \rightarrow dA | rB | mC | \epsilon
A \rightarrow oS
B \rightarrow eS
C \rightarrow iS

On a donc :

N = {S,A,B,C}
Σ = {d,r,m,o,e,i}

En appliquant les règles énumérées ci-dessus, on obtient l'automate suivant:

Automate.png

L'automate obtenu est non minimal (bien que déterministe), un algorithme de minimalisation enlèvera ainsi l'état qt inutile.

Articles connexes

Liens utiles

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Grammaire r%C3%A9guli%C3%A8re ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Grammaire rationnelle de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Grammaire Formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

  • Grammaire Régulière — Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d un langage régulier, en particulier dans le domaine des langages… …   Wikipédia en Français

  • Grammaire reguliere — Grammaire régulière Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d un langage régulier, en particulier dans le… …   Wikipédia en Français

  • Grammaire à états finie — Grammaire régulière Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d un langage régulier, en particulier dans le… …   Wikipédia en Français

  • Grammaire formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

  • Grammaire non contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… …   Wikipédia en Français

  • Grammaire linéaire — En informatique théorique, et notamment en théorie des langages, on appelle grammaire linéaire une grammaire algébrique dont tous les membres droits de règles contiennent au plus un symbole non terminal. Un langage linéaire est un langage qui est …   Wikipédia en Français

  • Grammaire régulière — Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d un langage régulier, en particulier dans le domaine des langages… …   Wikipédia en Français

  • Expression Rationnelle — Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères… …   Wikipédia en Français

  • Expression rationnelle — Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères… …   Wikipédia en Français