Dlaczego języki regularne (i te wyrażenia regularne) nazywane są „regularnymi”? Dużo prawidłowości występuje również w językach bezkontekstowych i innych rodzajach języków.
Przypuszczam, że na początku zastosowano przymiotnik „zwykły” w celu odróżnienia tego rodzaju języków od innych „nieregularnych” lub w jakiś sposób nienormalnych języków. Jeśli tak, to gdzie te inne typy i jaka była ich nieregularność ?
Odpowiedzi:
Szybka kontrola źródeł ujawnia, że Chomsky nazwał poziomy swojej hierarchii po prostu „typ 0, typ 1, typ 2, typ 3”. W przypisie wspomina, że jego typ 3 odpowiada „regularnym wydarzeniom” Kleene . Kleene napisał tam: Będziemy teraz opisywać klasę wydarzeń, które nazwiemy „regularnymi wydarzeniami”. (Chętnie przyjmiemy wszelkie sugestie dotyczące bardziej opisowego terminu).
Wydaje się zatem, że termin ten jest historycznym wypadkiem i w żadnym wypadku nie ma wpływu na stosunek zwykłych języków do języków bezkontekstowych.
źródło