Изменения

 Предположим, <tex>P</tex> допускает <tex>w</tex> по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении <tex>w</tex> в <tex>G</tex>. Правило автомата <tex>P</tex>, на основании которого применяется продукция, всегда одно. Но правило, скажем, <tex>δ\delta(q, a, X) = \{(r, Y1Y2Y_1Y_2...YkY_k)\}</tex>, может порождать много продукций грамматики <tex>G</tex>, с различными состояниями в позициях, отражающих состояния <tex>P</tex> после удаления каждого из <tex>Y1Y_1</tex>, <tex>Y2Y_2</tex>, ..., <tex>YkY_k</tex>. Однако, поскольку <tex>P</tex> детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению <tex>w</tex>.

Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L′ L` = L\$</tex>. Таким образом, цепочки языка <tex>L′L`</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L′L`</tex> имеет префиксное свойство, и <tex>L′ L` = N(P′P`)</tex> для некоторого ДМП-автомата <tex>P′P`</tex>. По [[#t1|теореме 1]] существует однозначная грамматика <tex>G′G`</tex>, порождающая язык <tex>N(P′P`)</tex>, т.е. <tex>L′L`</tex>.

Теперь по грамматике <tex>G′G`</tex> построим <tex>G</tex>, для которой <tex>L(G) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$</tex> как переменную грамматики <tex>G</tex> и введем продукцию <tex>\$ → ε\rightarrow \epsilon</tex>; остальные продукции <tex>G</tex> и <tex>G′G`</tex> одинаковы. Поскольку <tex>L(G′G`) = L′L`</tex>, получаем, что <tex>L(G) = L</tex>.

Утверждаем, что <tex>G</tex> однозначна. Действительно, левые порождения в <tex>G</tex> совпадают с левыми порождениями в <tex>G′G`</tex>, за исключением последнего шага в <tex>G</tex> — изменения <tex>\$</tex> на <tex>ε\epsilon</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G′G`</tex>. Поскольку <tex>G′G`</tex> однозначна, <tex>G</tex> также однозначна.