 |
langage régulier
| Wikipédia en français - L'encyclopédie libre | Download this dictionary |
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.
- 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 .
| Pour la suite, voir Wikipédia.org… |
© Cet article se sert du contenu de Wikipédia® et est autorisé sous les termes de la Licence de Documentation libre GNU et est distribué sous les termes de la licence Creative Commons Paternité-Partage des Conditions Initiales à l'Identique 3.0 non transposé.
