Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
'''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex>.<br/>
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex>.<br/>
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Таким образомЗначит, <tex>A \rightarrow Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>.<br/>
Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>.<br/>
Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1}, Y_{i_2}, ..., Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>.
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
