Pourquoi les langages réguliers (et à partir de ces expressions régulières) sont-ils appelés "réguliers"? Il y a beaucoup de régularité également dans les langues sans contexte et d'autres types de langues.
Je suppose que, au début, l'adjectif "régulier" a été utilisé pour différencier ce type de langues d'autres langues "non régulières" ou quelque peu anormales. Si oui, où étaient ces autres types et quelle était leur non-régularité ?
Réponses:
Une vérification rapide des sources révèle que Chomsky a appelé les niveaux de sa hiérarchie «type 0, type 1, type 2, type 3». Il mentionne dans une note de bas de page que son type 3 correspond à des «événements réguliers» de Kleene . Kleene a écrit: Nous décrirons actuellement une classe d'événements que nous appellerons «événements réguliers». (Nous serions heureux de recevoir toute suggestion concernant un terme plus descriptif.)
Il semblerait donc que le terme soit un accident historique, et en tout cas n'a aucune incidence sur la relation des langues régulières aux langues sans contexte.
la source