Доказательство леммы об эквивалентности допустимости пункта для активного префикса и достижимости этого пункта по эпсилон-переходам

Лемма. Об эквивалентности допустимости пункта для активного префикса и достижимости этого пункта по эпсилон-переходам

Пусть:

• $G$ - расширенная грамматика
• $I_G=(\_,\_,\_,q_0,\_)$ - Автомат LR(0)-пунктов, построенный по грамматике $G$

Тогда:

LR(0)-пункт $q=[B\to \bullet \beta ]$ грамматики $G$ допустим для активного префикса $\gamma$ некоторой r-формы $\iff$ состояние $q$ достижимо по $\epsilon$- переходам в автомате пунктов $I_G$ из некоторого состояния, соответствующего базисному пункту $[A\to {\beta }_1\bullet {\beta }_2]$, допустимого для $\gamma$

Доказательство: Доказательство леммы об эквивалентности допустимости пункта для активного префикса и достижимости этого пункта по эпсилон-переходам

Link to original