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

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

Последовательно применяем для данного ДАМП:

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

---

Связанные теоремы/определения

• Детерменированный автомат с магазинной памятью