Порождающий автомат — это абстракция автомата, при которой он рас сматривает как устройство, порождающее последовательность сообщений на выходе при переходе из одного состояния в другое.

Автомат-преобразователь — это абстрактный автомат, при котором он рассматривает как устройство преобразующее последовательность входных сообщений в последовательность выходных сообщений, при этом автомат изменяет свое состояние. Пример: компилятор.

Формальной грамматикой G называется алгебраическая система G = < V, W, P, I > , где V — алфавит терминальных знаков (основных) ,

W — алфавит нетерминальных знаков (вспомогательных) , (изначально предполагается, что V?W=?);

P — множество продукций (где правило вывода имеет вид P = {a®b, a, b? ( V ? W )*} , I — аксиома грамматики (начальный знак) , I ? W

Формальным языком L, порожденным формальной грамматикой G , L=L(G), называется всевозможные строки в терминальном алфавите, которые могут быть выведены из

аксиомы грамматики: L(G)={t ? V* | IG ? t}

18. Классификация языков по Хомскому.

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности.

Классификация грамматик[править | править вики-текст]

Согласно Хомскому, формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

Тип 0 — неограниченные[править | править вики-текст]

Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четвёрка (VT, VN, P, S), где[1]:

— алфавит (множество) терминальных символов — терминалов,

	— алфавит (множество) нетерминальных символов — нетерминалов,
		— словарь , причём
— конечное множество продукций (правил) грамматики,
	— начальный символ (источник).
Здесь		— множество всех строк над алфавитом , а	— множество непустых строк над
алфавитом .

К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:

,

где — любая непустая цепочка, содержащая хотя бы один нетерминальный[источник не указан 804 дня] символ, а — любая цепочка символов из алфавита.

Практического применения в силу своей сложности такие грамматики не имеют.