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.

On désigne l'ensemble des langages réguliers sur l'alphabet Σ par {\mathcal Rat}(\Sigma).

Ainsi {\mathcal Rat}(\Sigma) 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 \empty ainsi que tous les langages {a} où a\in\Sigma (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é \empty
  2. les langages a avec a\in\Sigma
  3. les langages L_1 + L_2, L_1\cdot L_2 et L_1^\star où L_1,L_2 \in {\mathcal Rat}(\Sigma)

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.

See also: Langage régulier, Automate fini, Classification des langages, Concaténation, Expression régulière, Fermeture de Kleene, Langage formel, Opération ensembliste, Théorème de Kleene