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