Dlaczego zwykłe języki nazywane są „zwykłymi”?


27

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ść ?


1
nie ma lepszego powodu niż powód, dla którego normalne podgrupy nazywane są „normalnymi”?
Sasho Nikolov

Odpowiedzi:


39

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.


6
pl1p

9
Artykuł pokazuje również, że musimy podziękować Kleenowi, jeśli zwykłe języki są nazywane „zwykłymi”, a nie „prewencyjnymi”.
gioele
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.