Pourquoi une langue régulière est-elle appelée «régulière»?

Je viens de terminer le premier chapitre de l' introduction à la théorie du calcul de Michael Sipser qui explique les bases des automates finis.

Il définit un langage régulier comme tout ce qui peut être décrit par un automate fini. Mais je n'ai pas pu trouver où il explique pourquoi une langue régulière est appelée "régulière?" Quelle est l'origine du terme «régulier» dans ce contexte?

REMARQUE: je suis un novice, alors essayez d'expliquer en termes simples!

Comme Kaveh le dit dans un commentaire, Kleene a donné le nom en arrière quand il a lancé la théorie des automates et les langages formels. Je crois que le terme était arbitraire, même si cela fait de nombreuses années que je n'ai pas lu son article original.

Les mathématiciens ont l'habitude de détourner les noms et adjectifs communs pour les objets et les propriétés mathématiques, parfois avec de bonnes raisons telles que des analogies ou des métaphores géométriques ou autres, et parfois arbitrairement. Il suffit de regarder "groupe", "anneau", "espace", "gerbe", "atlas", "collecteur", "champ" et ainsi de suite.

En fait, le terme «régulier» pour les langages à états finis, bien que toujours répandu dans la théorie des automates, n'est pas beaucoup utilisé dans son cousin algébrique, la théorie des semi-groupes finis ou l'algèbre abstraite en général. Pourquoi? Parce que le terme était déjà utilisé pour un semi-groupe qui est proche d'un groupe dans un sens technique spécifique, vous ne pouviez donc pas faire correspondre une langue régulière au sens de Kleene avec un semi-groupe régulier correspondant . Troisièmement, Kleene a défini un autre type d'événement appelé "défini", qui a été beaucoup étudié pendant un certain temps, mais s'est révélé peu fructueux. Aujourd'hui, des ensembles finis de langage jouent le rôle d'événements définis comme base d'événements réguliers.

Le terme préféré en algèbre est «rationnel» à la fois pour la classe de langues de Kleene et pour les semi-groupes et les monoïdes plus généraux. Cette utilisation reflète également une analogie importante entre le terme «rationnel» en algèbre comme solution d'une équation linéaire avec des coefficients entiers et le concept de séries de puissances rationnelles dans les automates et la théorie du langage formel.

Information additionnelle. L'article original de Kleene de 1951, intitulé "Représentation des événements dans les réseaux nerveux et les automates finis" peut être trouvé ici . Dans. 46 il règle l'arbitraire du terme "régulier" avec cette déclaration:

Nous allons maintenant décrire une classe d'événements que nous appellerons "événements réguliers". (Nous serions heureux de recevoir toute suggestion concernant un terme plus descriptif.)

Apparemment, personne n'a proposé un terme plus descriptif. ;-)

Comme c'est souvent le cas avec les articles fondateurs qui conduisent au développement intensif de nouveaux domaines entiers, la terminologie et les concepts sont presque méconnaissables dans les termes d'aujourd'hui. Tout d'abord, l'article portait sur les modèles de neurones, d'où l'utilisation d '«événements» au lieu de «langues» ou «ensembles». Le terme «événements» a persisté bien dans les années 60 et 70, même après que l'importance des concepts de Kleene pour les automates et les langages formels a largement dépassé toute valeur pour les neurosciences.

$a^*b$$a^*$$a^+$que nous utilisons aujourd'hui. La motivation de Kleene était d'éviter la chaîne vide (ou l'événement avec une durée nulle selon ses termes). C'était une intuition remarquablement prémonitoire puisque la théorie ultérieure a montré combien le choix est crucial d'inclure ou d'exclure la chaîne vide des définitions dans de nombreux contextes. Troisièmement, Kleene a défini un concept appelé "événements définis" et en a développé des événements réguliers, mais de nos jours, nous utilisons des ensembles finis à cet effet. Les événements définis ont été étudiés pendant un certain temps, mais se sont avérés beaucoup moins importants que les événements / ensembles / langues habituels.

Quoi qu'il en soit, une lecture complète de cet article ne vaut probablement pas le temps de quiconque aujourd'hui, sauf à des fins historiques. Je l'ai juste survolé pour les définitions et les idées cruciales, et c'était amusant.

J'ai toujours compris que le terme "régulier" signifie qu'il est basé sur un motif qui se répète. Après avoir énuméré toutes les chaînes d'une certaine longueur, vous les avez toutes vues. Il n'y aura rien de nouveau par la suite.

(Ce n'est qu'une vague intuition bien sûr.)