Содержание
- 2. Ю.Г.Карпов Автоматы и формальные языки Структура курса Конечные автоматы-распознаватели – 4 л Лекция 1. Формальные языки.
- 3. Ю.Г.Карпов Автоматы и формальные языки Формальные языки Формальный язык – это некоторое множество конечных цепочек, построенных
- 4. Ю.Г.Карпов Автоматы и формальные языки Автоматные языки Конечных автоматов-распознавателей бесконечное число. И автоматных языков тоже бесконечное
- 5. Ю.Г.Карпов Автоматы и формальные языки Представление конечных автоматов aaba ∈ LA; aabbb ∉ LA. А=(S, Σ,
- 6. Необходимость изучения автоматных языков и конечных автоматов-распознавателей Автоматными языками являются многие языки: Специализированные языки Языки управления
- 7. Примеры языков и распознающих их конечных автоматов Пример 1. Язык: цепочки из 0 и 1, заканчивающиеся
- 8. Операции над автоматами: тримминг
- 9. Ю.Г.Карпов Автоматы и формальные языки Полный конечный автомат Если переходы в автомате-распознавателе под воздействием некоторых событий
- 10. Ю.Г.Карпов Автоматы и формальные языки Приведение конечного автомата Операция “приведения” (trimming) конечного автомата: выбрасывание всех состояний,
- 11. Ю.Г.Карпов Автоматы и формальные языки Распознавание дополнения автоматного языка КА А распознает цепочку, если она переводит
- 12. Ю.Г.Карпов Автоматы и формальные языки Распознаватель дополнения автоматного языка 1: Заданный КА с неполностью определенными переходами
- 13. Синхронная композиция двух автоматов-распознавателей Пересечение автоматных языков
- 14. Синхронная композиция автоматов – два автомата, работающие синхронно от одного входа Ю.Г.Карпов Автоматы и формальные языки
- 15. Ю.Г.Карпов Автоматы и формальные языки Синхронная композиция автоматов. Максимальное число достижимых состояний синхронной композиции автоматов А
- 16. Ю.Г.Карпов Автоматы и формальные языки Пример. Статический анализ текста || программ Правильные цепочки событий обращения к
- 17. Ю.Г.Карпов Автоматы и формальные языки Синтез супервизоров – новая идея построения систем логического управления Автомат А
- 18. Синтез супервизоров - “горячая” область исследований INTERNATIONAL WORKSHOP ON DISCRETE EVENT SYSTEMS IEEE INT CONFERENCE ON
- 19. Эквивалентность двух автоматов-распознавателей
- 20. Ю.Г.Карпов Автоматы и формальные языки Эквивалентность двух конечных автоматов-распознавателей – как проверить? Определение. Два конечных автомата-распознавателя
- 21. Ю.Г.Карпов Автоматы и формальные языки Эквивалентные автоматы-распознаватели. Теорема Мура Доказательство. Два автомата будут эквивалентными тогда и
- 22. Ю.Г.Карпов Автоматы и формальные языки Эквивалентные автоматы-распознаватели Два автомата будут эквивалентными тогда и только тогда, когда
- 23. Минимизация конечных автоматов-распознавателей
- 24. Ю.Г.Карпов Автоматы и формальные языки Минимизация конечных автоматов-распознавателей Существует единственный (с точностью до изоморфизма, т.е. именования
- 25. Пример неминимального автомата Подмножества состояний {0,2}; {1,5,7}; {3,6}; {4} – классы эквивалентных состояний. Как найти эту
- 26. Ю.Г.Карпов Автоматы и формальные языки Минимизация конечных автоматов - распознавателей Построим на множестве состояний автомата А
- 27. Ю.Г.Карпов Автоматы и формальные языки Конечный автомат с эквивалентными состояниями π0 = {0, 1, 2, 5,
- 28. Ю.Г.Карпов Автоматы и формальные языки Алгоритм построения эквивалентности π Так же, как и для автоматов-преобразователей, рассматриваем
- 29. Ю.Г.Карпов Автоматы и формальные языки Минимальный конечный автомат-распознаватель π0 = {0, 1, 2, 5, 7}=A; {3,
- 30. Ю.Г.Карпов Автоматы и формальные языки Представление отношения эквивалентности матрицей Манипуляции с отношениями эквивалентности удобно выполнять с
- 31. Ю.Г.Карпов Автоматы и формальные языки Эквивалентное представление алгоритма построения отношения эквивалентности Алгоритм: для каждой пары состояний
- 32. Недетерминированные конечные автоматы-распознаватели
- 33. Ю.Г.Карпов Автоматы и формальные языки Недетерминированные конечные автоматы-распознаватели Два начальных состояния, пустой переход, неоднозначный переход –
- 34. Ю.Г.Карпов Автоматы и формальные языки Основное правило для недетерминированных конечных автоматов-распознавателей Как понимать коллизии: а) несколько
- 35. Ю.Г.Карпов Автоматы и формальные языки Как “работает” недетерминированный КА Каковы все возможные реакции на а а
- 36. Ю.Г.Карпов Автоматы и формальные языки Формальное определение недетерминированного КА Недетерминированный конечный автомат-распознаватель А=(S, Σ, s0, δ,
- 37. Ю.Г.Карпов Автоматы и формальные языки Приведение к НДКА без ε-переходов Недетерминированный конечный автомат-распознаватель А=(S, Σ, s0,
- 38. Ю.Г.Карпов Автоматы и формальные языки Чем удобны НДКА? Пример 1 Строим НЕдетерминированный конечный автомат: Строим детерминированный
- 39. Ю.Г.Карпов Автоматы и формальные языки Чем удобны НДКА? Пример 2 Задача: Построить КА с входным алфавитом
- 40. Ю.Г.Карпов Автоматы и формальные языки Чем удобны НДКА? Пример 3 Задача: Построить КА с входным алфавитом
- 41. Ю.Г.Карпов Автоматы и формальные языки Распознающая мощность недетерминированных КА Ясно, что детерминированные конечные автоматы – подкласс
- 42. Ю.Г.Карпов Автоматы и формальные языки Распознающая мощность недетерминированных КА Теорема (Рабина-Скотта). Для любого недетерминированного конечного автомата
- 43. Ю.Г.Карпов Автоматы и формальные языки От недетерминированного автомата к эквивалентному детерминированному автомату Множество начальных состояний –
- 44. Минимизация алгоритмом “треугольника” Ю.Г.Карпов Автоматы и формальные языки π∞ = {q0, q4, q7}; {q2, q5, q6};
- 45. Ю.Г.Карпов Автоматы и формальные языки Минимизация построенного детерминированного автомата, эквивалентного исходному У детерминированного автомата В, эквивалентного
- 46. Ю.Г.Карпов Автоматы и формальные языки Пример перехода от недетерминированного автомата к эквивалентному детерминированному 0, 1 Автомат
- 47. Ю.Г.Карпов Автоматы и формальные языки Зачем нужны недетерминированные КА? Пример 2 Задача: Построить КА с входным
- 48. Операции над автоматными языками и конечными автоматами-распознавателями
- 49. Ю.Г.Карпов Автоматы и формальные языки Используя переход, помеченный пустым символом ε, ЛЮБОЙ конечно-автоматный распознаватель можно представить
- 50. Ю.Г.Карпов Автоматы и формальные языки Операции над автоматными языками Теорема. Если L1 и L2 – автоматные
- 51. Ю.Г.Карпов Автоматы и формальные языки Операции над автоматами и автоматными языками, дающие в результате автоматные языки
- 52. Резюме: операции над автоматными языками Теорема. Множество автоматных языков замкнуто относительно операций: - дополнения, - объединения,
- 53. Пример применения недетерминированных КА: Римская система счисления
- 54. Что написано на золотой медали Альфреда Нобиля? Ю.Г.Карпов Автоматы и формальные языки MDCCCXXXIII - MDCCCXCVI 1833
- 55. Ю.Г.Карпов Автоматы и формальные языки I = 1 V = 5 X = 10 L =
- 56. Ю.Г.Карпов Автоматы и формальные языки Правила построения римских чисел: Википедия Если меньшие цифры следуют за большими,
- 57. Ю.Г.Карпов Автоматы и формальные языки Правила построения римских чисел: формально (1) Меньшие цифры обычно следуют за
- 58. Ю.Г.Карпов Автоматы и формальные языки Правила построения римских чисел: формально (2) Меньшие могут предшествовать большим. Меньшая
- 59. Ю.Г.Карпов Автоматы и формальные языки Правила построения римских чисел: формально (3) Меньшая цифра либо первая в
- 60. Ю.Г.Карпов Автоматы и формальные языки Возможные значения римских чисел I = 1 V = 5 X
- 61. Ю.Г.Карпов Автоматы и формальные языки Правила построения римских чисел: формально (4) I = 1 V =
- 62. Ю.Г.Карпов Автоматы и формальные языки Недетерминированные автоматы: общее понимание Недетерминированные автоматы нельзя рассматривать, как физические устройства,
- 63. Ю.Г.Карпов Автоматы и формальные языки Заключение Операции над КА-распознавателями: “trimming” – приведение, т.е. выбрасывание недостижимых и
- 64. Ю.Г.Карпов Автоматы и формальные языки Заключение (2) Существует простой алгоритм проверки эквивалентности КА. Для такой проверки
- 65. Ю.Г.Карпов Автоматы и формальные языки Спасибо за внимание
- 66. Ю.Г.Карпов Автоматы и формальные языки Эквивалентные автоматы-распознаватели: ПРИМЕРЫ ≈ ≈ Все состояния, из которых НЕдостижимы финальные
- 68. Скачать презентацию