Содержание
- 2. Теория нормальных алгоритмов была разработана советским математиком Андреем Андреевичем Марковым в конце 1940-х годов. При изучении
- 3. Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно
- 4. Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга НАМ —
- 5. Алфавитом будем называть любое непустое множество. Его элементы называются буквами, а любая последовательность букв – словами
- 6. Формулой подстановки называется запись вида α→β (читается «α заменить на β»), где α и β –
- 7. Правила выполнения НАМ Прежде всего, задается некоторое входное слово Р. Работа НАМ сводится к выполнению последовательности
- 10. Марковской подстановкой (Р,Q) называется следующая операция над словами: в заданном слове R находят первое вхождение слова
- 11. Замечание: 1) Полученное слово называется результатом применения марковской подстановки (Р,Q) к слову R 2) Если первого
- 12. Частными случаями марковских подстановок являются подстановки с пустыми словами: (Λ,Q), (P, Λ), (Λ,Λ)
- 13. Для обозначения марковской подстановки (Р,Q) используют запись Р → Q Эту запись называют формулой подстановки (Р,Q)
- 14. Пример Данное слово: 521421 Подстановка: 21 → 3 Результат подстановки: 5343
- 15. Пример Данное слово: 521421 Подстановка: 21 ו→ Λ Результат подстановки: 5421
- 16. Пример Данное слово: 521421 Подстановка: 25 → 7 Результат подстановки: Не применима
- 18. Скачать презентацию