Почему обычные языки называются «обычными»?

27

Почему регулярные языки (и из этих регулярных выражений) называются "регулярными"? Существует много закономерностей и в контекстно-свободных языках других типов языков.

Я предполагаю, что в начале прилагательное «обычный» использовалось для того, чтобы отличать этот тип языков от других «нерегулярных» или каким-то ненормальных языков. Если да, то где эти другие типы и какова была их нерегулярность ?

Gioele
источник
1
нет лучшей причины, чем причина, почему нормальные подгруппы называются «нормальными»?
Сашо Николов
2
@SashoNikolov: math.stackexchange.com/questions/898977/…
Джошуа

Ответы:

39

Быстрая проверка источников показывает, что Хомский назвал уровни своей иерархии просто «тип 0, тип 1, тип 2, тип 3». В сноске он упоминает, что его тип 3 соответствует «регулярным событиям» Клини . Клини написала там: « Сейчас мы опишем класс событий, которые мы назовем« обычными событиями ». (Мы будем рады любым предложениям относительно более описательного термина.)

Таким образом, может показаться, что этот термин является исторической случайностью и в любом случае не имеет отношения к отношениям обычных языков с языками без контекста.

Эмиль Йержабек поддерживает Монику
источник
6
pl1p
9
В документе также показано, что мы должны поблагодарить Клин, если регулярные языки называются «обычными», а не «предвзятыми».
Gioele