Теорема. Существование эквивалентного ДАМП с магазинной памятью, распознающего слова при пустом стеке

Пусть

Язык $L$ распознается ДАМП $M$

Тогда

Существует эквивалентный ему ДАМП $M^{\prime }$, который распознает $L$ при помощи пустого стека

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