Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Langage régulier

Un langage régulier ou langage rationnel, ou encore langage de type 3 dans la hiérarchie de Chomsky, est un langage formel que l'on peut définir grâce à une expression régulière sur un alphabet.

On désigne l'ensemble des langages réguliers sur l'alphabet Σ par .

Ainsi est le plus petit ensemble de langages stable par la concaténation de langages (notée « . »), par l'union (notée « + ») et par la fermeture de Kleene (notée « * ») et qui contienne ainsi que tous les langages {"a"} où (que l'on notera abusivement a, tout simplement; de même que {ε}, le langage contenant le mot vide, est noté ε).

Les langages rationnels sur l'alphabet Σ peuvent aussi être définis récursivement comme étant :

1. le langage vide, noté
2. les langages a avec
3. les langages et où

Un résultat important concernant les langages rationnels est le théorème de Kleene, qui affirme que l'ensemble des langages rationnels sur Σ est exactement l'ensemble des langages reconnaissables par automate fini sur Σ. En d'autres termes, à tout automate fini on peut associer une expression régulière qui définit le langage reconnu par l'automate, et réciproquement. Notons qu'il n'y a pas bijection car plusieurs automates différents peuvent reconnaître un même langage, et de même il existe plusieurs expressions régulières pour le définir.