Классификация распознавателей

Для каждого класса грамматик из иерархии Хомского существует класс распознавателей, определяющих тот же класс языков. Чем шире класс грамматик, тем сложнее класс соответствующих распознавателей.

Для языков типа 0 распознавателями являются машины Тьюринга.

Распознаватели КЗ-языков называются линейными ограниченными автоматами (машины Тьюринга с конечным объемом ленты).

Распознавателями для КС-языков являются автоматы с магазинной памятью.

Для регулярных языков распознавателями служат конечные автоматы.

Регулярные грамматики и языки

Регулярные выражения

Регулярный язык L в некотором алфавите S представляет собой регулярное множество строк.

Определение Регулярное множество есть Æ, либо {e}, либо { а } для некоторого а ÎS, либо множество, которое можно получить из указанных множеств путем применения конечного числа операций сцепления, объединения и итерации.

В основе метода определения регулярности заданного языка лежит лемма о разрастании языка.