langage régulier
Langage rationnel
En
théorie des langages, les
langages rationnels ou
langages réguliers ou encore
langages reconnaissables peuvent être décrits de plusieurs façons équivalentes :
- ce sont les langages décrits par les expressions régulières ou rationnelles, d'où le nom de langages réguliers ;
- ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les opérations rationnelles, à savoir l'union, le produit et l'étoile de Kleene, d'où le nom de langages rationnels ;
- ce sont les langages reconnus par des automates finis, d'où le nom de langages reconnaissables.
Ce sont aussi :
- les langages dont le monoïde syntaxique est fini,
- les langages qui admettent une description dans la logique monadique du second ordre avec successeur,
- les langages de type 3 dans la hiérarchie de Chomsky : ce sont les langages qui peuvent être engendrés par une grammaire régulière, c'est-à-dire une grammaire linéaire droite (ou linéaire gauche),
- les langages reconnus par des machines de Turing qui n'écrivent pas sur leur bande (ce sont aussi les ) ;
- les langages reconnus par des .