Определения
- Детерменированный автомат с магазинной памятью
- Управляющая таблица МП-автомата
- Недетерменированный автомат с магазинной памятью
- Конфигурация автомата с магазинной памятью
- Распознаваемость слов автоматами с магазинной памятью
- Язык, распознаваемый автоматом с магазинной памятью
- Протокол обработки слова
- Распознаваемость слов автоматами с магазинной памятью при пустом стеке
- Язык, распознаваемый автоматом с магазинной памятью при пустом стеке
- Эквивалентность ДАМП
Теоремы/следствия
ДАМП
- Теорема. Существование эквивалентного ДАМП с магазинной памятью, распознающего слова при пустом стеке
- Теорема. Существование эквивалентного ДАМП с пустым начальном стеком
- Следствие. Существование эквивалентного ДАМП, распознающего слова при пустом стеке и с пустым начальным стеком
- Лемма. Об упрощении ДМПА
- Алгоритм. Об упрощении ДМПА
НАМП
- Теорема. Совпадение класса контекстно-свободных языков и класса языков распознаваемых НАМП
- Есть еще какое-то следствие. Похуй?
Вопросы
14
