Автоматы с магазинной памятью презентация
Содержание
- 2. Определение 14.21 Автомат с магазинной памятью – это односторонний недетерминированный распознаватель.
- 3. Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства;
- 4. В определении функции переходов запись (q, ) (q, a, Z)
- 5. Определение 14.22 если = , то верхний символ удаляется из
- 6. — неиспользованная часть входной цепочки; первый символ цепочки находится
- 7. Определение 14.23 Начальной конфигурацией МП-автомата P называется конфигурация вида (q0, ,
- 8. Определение 14.24 Заключительной конфигурацией МП-автомата P называется конфигурация вида: (q, ,
- 9. Определение 14.26 Говорят, что цепочка допускается МП –автоматом P, если
- 10. Пример 14.3. Пример 14.3. Построим МП –автомат, определяющий язык L={0n1n |
- 11. Построим МП –автомат, определяющий язык L={wwR | w{0,1}+}. Построим МП –автомат,
- 12. Определение 14.28 Расширенный автомат с магазинной памятью (МП- автомат) – это
- 13. 4) - отображение множества Q ( {})
- 14. В определении функции переходов запись (q, ) (q, a, Z)
- 15. если = , то верхний символ удаляется из магазина (магазинный
- 16. Пример 14.5. Пример 14.5. Построим расширенный МП –автомат, определяющий язык L={wwR
- 17. Определение 14.29 МП-автомат P = (Q, , Г, , q0, Z0,
- 18. Лемма 14.5 Пусть P = (Q, , Г, , q0, Z0,
- 19. Так как выполнено (q, w, A) Рn' (q', , ),
- 20. Тогда для любых возможна последовательность Тогда для любых
- 21. Определение 14.30 Пусть P = (Q, , Г, , q0, Z0,
- 22. Лемма 14.6 Пусть L = L(P) для некоторого МП-автомата P =
- 23. 3. для любых q F, z Г {Z'}
- 24. Лемма 14.7 Пусть P = (Q, , Г, , q0, Z0,
- 25. 1. если правило вида A P, то (q,
- 26. Предположим, что при всех m', таких, что 1 < m' <
- 27. База индукции. Если n =1 и (q, w, A) 1 (q,
- 28. A X1X2… Xk A X1X2… Xk *
- 29. Пример 14.6. Пример 14.6. Построим МП –автомат P, для которого L(P)
- 30. Определение 14.31 Пусть G = (N, , P, S) – КС-грамматика
- 31. Лемма 14.9 Пусть G = (N, , P, S) – КС-грамматика.
- 32. Докажем, что справедливо L(G) = L(R). Докажем, что справедливо L(G) =
- 33. Допустим, что цепочка состоит только из терминалов. Тогда =х и
- 34. 2. Теперь докажем обратное включение L(R) L(G), т.е. покажем, что
- 35. (q, ху, #) m–1 (q, y, #) (q, y, #
- 36. Пример 14.7. Построим восходящий анализатор R для грамматики G примера 7.5.
- 37. Теорема 14.3 Язык L является КС-языком тогда и только тогда, когда
- 38. Скачать презентацию
Слайды и текст этой презентации