Similar presentations:
Машины Тьюринга. Алгоритмы и структуры данных
1.
Алгоритмы и структурыданных
2022-2023 учебный год
Нестеров Роман Александрович, PhD & Бессмертный Александр Игоревич
Департамент программной инженерии
2.
План1. Повторить построение конечного автомата для заданного
регулярного автомата.
2. Несколько слов о машине Тьюринга.
3. Какую задачу решает заданная машина Тьюринга?
4. Построение машины Тьюринга по описанию задачи/языка.
5. Пределы вычислимости/разрешимости.
6. Иерархия сложности алгоритмов по времени и по памяти.
3.
Регулярные выражения иавтоматы
4.
УпражнениеПо заданному регулярному выражению построить конечный
автомат, распознающий этот регулярный язык в алфавите {a, b}.
•(a + ab)*
5.
О машине Тьюринга6.
Автоматы и машины Тьюринга• Конечные автоматы не имеют оперативной памяти для
промежуточного хранения
• Автоматы с магазинной памятью моделируют работу
вычислительных устройств со стековой памятью
• Машины Тьюринга (1936)
• Оперируют с неограниченной слева и справа лентой, с которой
можно писать и на которую можно записывать символы
• «Контролируется» конечным автоматов
• Моделируют работу любого компьютера – Тезис Черча-Тьюринга
• НЕ может решить все возможные вычислительные задачи
7.
Машина Тьюринга• Входной алфавит Σ.
• Алфавит ленты Γ = Σ ∪