Классификация грамматических формальных систем по их порождающей способности

1. Рекурсивно перечислимые имеют неограниченные правила; по обе стороны правил подстановки может находиться любое количество терминальных и нетерминальных символов, как в правиле
А В —> С

2. Контекстно-зависимые ограничены лишь тем, что в правой части правил должно находиться по меньшей мере столько же символов, сколько и в левой части.

3. Контекстно-свободные левая часть каждого правила состоит из одного нетерминального символа.

4. Регулярные. Каждое правило имеет один нетерминальный символ в левой части и терминальный символ, за которым может следовать или не следовать нетерминальный символ, в правой части.