Классификация грамматик Хомского

Согласно Ноаму Хомоски, существует четыре типа грамматик - Тип 0, Тип 1, Тип 2 и Тип 3. В следующей таблице показано, чем они отличаются друг от друга.

Тип грамматики	Грамматика принята	Принимаемый язык	Автомат
Тип 0	Неограниченная грамматика	Рекурсивно перечисляемый язык	Машина Тьюринга
Тип 1	Контекстно-зависимая грамматика	Контекстно-зависимый язык	Линейно-ограниченный автомат
Тип 2	Бесконтекстная грамматика	Бесконтекстный язык	Выталкивающий автомат
Тип 3	Обычная грамматика	Обычный язык	Конечный автомат

Взгляните на следующую иллюстрацию. Он показывает объем каждого типа грамматики -

Тип - 3 Грамматика

Type-3 grammarsгенерировать обычные языки. Грамматики типа 3 должны иметь один нетерминал с левой стороны и с правой стороны, состоящий из одного терминала или одного терминала, за которым следует один нетерминал.

Продукция должна быть в форме X → a or X → aY

где X, Y ∈ N (Нетерминальный)

а также a ∈ T (Терминал)

Правило S → ε разрешено, если S не появляется справа ни от одного правила.

пример

X → ε 
X → a | aY
Y → b

Тип - 2 Грамматика

Type-2 grammars генерировать контекстно-свободные языки.

Продукция должна быть в форме A → γ

где A ∈ N (Нетерминальный)

а также γ ∈ (T ∪ N)* (Строка терминалов и нетерминалов).

Эти языки, генерируемые этими грамматиками, распознаются недетерминированным автоматом выталкивания.

пример

S → X a 
X → a 
X → aX 
X → abc 
X → ε

Тип - 1 Грамматика

Type-1 grammarsсоздавать контекстно-зависимые языки. Продукция должна быть в форме

α A β → α γ β

где A ∈ N (Нетерминальный)

а также α, β, γ ∈ (T ∪ N)* (Строки терминалов и нетерминалов)

Струны α а также β может быть пустым, но γ не должно быть пустым.

Правило S → εразрешено, если S не появляется справа от любого правила. Языки, порожденные этими грамматиками, распознаются линейно ограниченным автоматом.

пример

AB → AbBc 
A → bcA 
B → b

Тип - 0 Грамматика

Type-0 grammarsгенерировать рекурсивно перечислимые языки. У постановок нет ограничений. Это любая грамматика фазовой структуры, включая все формальные грамматики.

Они генерируют языки, распознаваемые машиной Тьюринга.

Спектакли могут быть в виде α → β где α представляет собой строку терминалов и нетерминалов с хотя бы одним нетерминальным и α не может быть нулевым. β представляет собой цепочку терминалов и нетерминалов.

пример

S → ACaB 
Bc → acB 
CB → DB 
aD → Db