Langage rationnel - Définition

Historique

Dans les années 1940, Warren McCulloch et Walter Pitts ont décrit le système nerveux en modélisant les neurones par des automates simples. Le logicien Stephen Cole Kleene a ensuite décrit ces modèles en termes d'ensembles réguliers, dans un article intitulé Représentation des évènements dans les réseaux nerveux et Automates finis.

Dans les années 1950, A. Nerode, J. Myhill, D. A. Huffman et E. F. Moore établissent le lien avec les congruences et l'algorithme de minimisation des automates déterministes. En 1959, Michael Rabin et Dana Scott proposent le premier traitement mathématique et rigoureux de ces concepts dans un article célèbre qui leur vaut le Prix Turing et qui contribue à faire démarrer l'étude de ces langages, dans leur célèbre article Automates finis et leurs problèmes de décision.

Ken Thompson a implémenté cette notation dans l'éditeur qed, puis l'éditeur ed sous Unix, et finalement dans grep. Depuis lors, les expressions rationnelles ont été largement utilisées dans les utilitaires tels que lex ainsi que dans les langages de programmation nés sous Unix, tels que expr, awk, Perl, Python... Une bonne partie d'entre eux reposent sur la bibliothèque regex, créée par Henry Spencer.

Exemples et contre-exemples

Les langages suivants sont rationnels :

• L'ensemble des notations décimales de nombres naturels sur l'alphabet: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Les langages finis.
• L'ensemble des mots qui contiennent un mot donné.
• L'ensemble des mots qui contiennent un nombre pair de "1".
• L'ensemble des mots qui sont l'écriture en binaire d'un entier congruent à 2 modulo 5.

En revanche, les langages suivants ne sont pas rationnels :

• L'ensemble de mots {aⁿbⁿ : n ≥ 0 }
• Une expression bien parenthésée est obtenue comme étant soit () soit (e) où e est elle-même bien parenthésée. L'ensemble des expressions bien parenthésées ne forme pas un langage rationnel car son intersection avec le langage rationnel (*)* n'est pas rationnelle (c'est le langage précédent à un changement de symboles près).
• L'ensemble des palindromes.