Пример 4. Очевидно, что грамматики из примеров 2 и 3, а также задачи 2 являются контекстно-зависимыми, поскольку правые части их правил не короче левых частей

Очевидно, что грамматики из примеров 2 и 3, а также задачи 2 являются контекстно-зависимыми, поскольку правые части их правил не короче левых частей. Заметим, что для грамматики из примера 1 этому условию не удовлетворяет последнее правило:

A → ε

• Тип G2 (контекстно-свободные или КС-грамматики). Грамматику G называют грамматикой типа 2, если каждое ее правило имеет вид:

.Вместо термина «контекстно-свободная грамматика» часто используют аббревиатуру cfg (context-free grammar).

Замечание.

Правило вида A→β позволяет заменить A на β независимо от контекста, в котором появляется A.