¿Por qué los idiomas regulares se llaman "regulares"?

27

¿Por qué los lenguajes regulares (y de esas expresiones regulares) se llaman "regulares"? Hay mucha regularidad también en los idiomas sin contexto de otros tipos de idiomas.

Supongo que, al principio, el adjetivo "regular" se ha utilizado para diferenciar ese tipo de idiomas de otros lenguajes "no regulares" o de alguna manera anormales. Si es así, ¿dónde estaban estos otros tipos y cuál era su falta de regularidad ?

gioele
fuente
1
¿No hay mejor razón que la razón por la cual los subgrupos normales se llaman "normales"?
Sasho Nikolov
2
@SashoNikolov: math.stackexchange.com/questions/898977/…
Joshua Grochow

Respuestas:

39

Una revisión rápida de las fuentes revela que Chomsky llamó a los niveles de su jerarquía simplemente "tipo 0, tipo 1, tipo 2, tipo 3". Menciona en una nota al pie que su tipo 3 corresponde a "eventos regulares" de Kleene . Kleene escribió allí: A continuación describiremos una clase de eventos que llamaremos "eventos regulares". (Agradeceríamos cualquier sugerencia sobre un término más descriptivo).

Por lo tanto, parecería que el término es un accidente histórico y, en cualquier caso, no tiene relación con la relación de los idiomas regulares con los idiomas libres de contexto.

Emil Jeřábek apoya a Monica
fuente
66
pags-l-1pags
99
El documento también muestra que debemos agradecer a Kleen si los idiomas regulares se llaman "regulares" y no "prensibles".
gioele