Loading AI tools
De Wikipédia, l'encyclopédie libre
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.
Une grammaire régulière peut être « à gauche » ou « à droite ».
où , sont des symboles non-terminaux et un symbole terminal.
où , sont des symboles non-terminaux et un symbole terminal. De plus, comme pour toutes grammaires, on considère un non-terminal particulier appelé axiome et noté .
La grammaire suivante est une grammaire régulière à droite :
Avec la grammaire précédente, on peut engendrer le mot . En effet : .
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.
Considérons la grammaire ci-dessus. L'automate correspondant est le suivant :
La suite de dérivations correspond à la lecture du mot dans l'automate où on passe successivement dans les états : S, A, S, B, S, C, S.
Soit une grammaire régulière à droite , alors l'automate équivalent à G est défini tel que:
La lecture de permet de construire . Pour chaque :
Le même type de jeu de règles peut être établi pour une grammaire régulière à gauche.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.