175
правок
Изменения
→Корректность построения
*Переход. Предположим, что <tex> (q,w,S)\vdash^*(q,w_i,\alpha_i) </tex>. Заметим, что шаг порождения <tex> y_i \Rightarrow y_{i+1}</tex> включает замену некоторой переменной <tex> A </tex> ее продукцией <tex> \beta </tex>. Правило 1 построения МП-автомата позволяет на заменить <tex> A </tex> на вершине стека на цепочку <tex> \beta </tex>, а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО <tex> (q,y_{i+1},\alpha_{i+1}) </tex>.
*Также заметим, что <tex> \alpha_n = \epsilon</tex>. Таким образом <tex> (q,w,S)\vdash^*(q,\epsilon,\epsilon) </tex>, т.е допускает <tex> P </tex> по пустому стеку.
{{Теорема|about= О совпадении КС-языков и множества языков МП-автоматаУтверждение|statement= Если МП-автомат <tex> P </tex> построен по грамматике <tex> G </tex> по с использованием указанной выше конструкции, то <tex> N(P) \geq L(G) </tex>
|proof= Очевидно из того, что мы доказали корректность построения.
}}
