Por que os idiomas regulares (e a partir dessas expressões regulares) são chamados de "regulares"? Há muita regularidade também em idiomas sem contexto, outros tipos de idiomas.
Suponho que, no começo, o adjetivo "regular" tenha sido usado para diferenciar esse tipo de idioma de outros idiomas "não regulares" ou de alguma forma anormais. Em caso afirmativo, onde esses outros tipos e qual a sua não regularidade ?
Respostas:
Uma rápida verificação das fontes revela que Chomsky chamou os níveis de sua hierarquia apenas de “tipo 0, tipo 1, tipo 2, tipo 3”. Ele menciona em uma nota de rodapé que seu tipo 3 corresponde a "eventos regulares" de Kleene . Kleene escreveu lá: Atualmente, descreveremos uma classe de eventos que chamaremos de "eventos regulares". (Gostaríamos de receber sugestões sobre um termo mais descritivo.)
Parece, portanto, que o termo é um acidente histórico e, em qualquer caso, não tem relação com a relação de linguagens regulares com linguagens livres de contexto.
fonte