Лемма. Об эквивалентности контекстно свободной грамматики эпсилон-свободной ацикличной грамматике с ограничениями на вид правил 2

Доказательство

По лемме можно считать, что данную КС-грамматику приведенной, эпсилон-свободной, ацикличной, с правилами вида:

Тогда пусть в грамматике есть “плохое” правило вида $A_1\to A_2$:

Алгоритм, основанный на лемме, но в других формулировках, удаляющий все цепные пары

0. Пусть $G^{\prime }=G$ - строящаяся грамматика, которую прогнали через лемму.
1. Найти все цепные пары в исходной грамматике $G$
2. Для каждой цепной пары $(A,B)$ добавить в строющуюся грамматику $G^{\prime }$ все правила вида $A\to \alpha ,B\to \alpha$ - нецепные правила из исходной $G$
3. Удалить все найденные цепные правила из $G^{\prime }$

Алгоритм, сформулированный chatgpt

Похож на алгоритм выше

---

Связанные теоремы/определения

• Цепная пара
• Цепное правило