Автоматы и формальные языки

Здесь вы можете просмотреть и скачать доклад по теме «Автоматы и формальные языки», размещенный в категории «Устройства и комплектующие», который поможет вам успешно провести свое мероприятие или подготовиться к занятию.

Информация о презентации

Автоматы и формальные языки
Раздел:Устройства и комплектующие
Слайдов:67
Слов:1630
Символов:13493
Просмотров:34
Скачиваний:2
Загрузка:онлайн
Размер:4.27 MB
Тип:ppt / pptx для PowerPoint/Impress
Теги:#автомат, #язык, #распознавател, #эквивалентн, #состоян, #конечн, #автоматн, #недетерминирова, #цифр, #построен

Похожие презентации об устройстве и комплектующих

Готовые презентации об устройстве и комплектующих

Содержание слайда №1 (27 знаков, 4 слова)

Автоматы и формальные языки

Содержание слайда №2 (424 знака, 44 слова)

Структура курса Конечные автоматы-распознаватели – 4 л Лекция 1. Формальные языки. Примеры языков. Грамматики. КА Лекция 2. Теория конечных автоматов-распознавателей Лекция 3. Трансляция автоматных языков Лекция 4. Регулярные множества и регулярные выражения Порождающие грамматики Хомского – 3 л Атрибутные трансляции и двусмысленные КС-грамматики – 2 л Распознаватели КС-языков и трансляция – 6 л Дополнительные лекции 2 л

Содержание слайда №3 (16 знаков, 2 слова)

Формальные языки

Содержание слайда №4 (231 знак, 27 слов)

Автоматные языки Конечных автоматов-распознавателей бесконечное число. И автоматных языков тоже бесконечное число. Но существуют языки, которые не являются автоматными. Например, язык вложенных скобок L={anbn | n0} – неавтоматный.

Содержание слайда №5 (32 знака, 3 слова)

Представление конечных автоматов

Содержание слайда №6 (741 знак, 87 слов)

Необходимость изучения автоматных языков и конечных автоматов-распознавателей Автоматными языками являются многие языки: Специализированные языки Языки управления ОС Многие скриптовые языки Фрагменты языков высокого уровня (имена, константы, комментарии, . . . ) Все регулярные языки (т. е. языки, задаваемые регулярными выражениями). . . . . . Автоматные языки составляют лишь подкласс (довольно узкий) всех возможных языков Примеры неавтоматных языков: - язык вложенных скобок (и любой язык, с вложенными конструкциями) - множество цепочек с одинаковым числом вхождений символов а и b - все языки программирования высокого уровня, естественные языки. . . . Существует множество важных и интересных практических применений автоматных языков

Содержание слайда №7 (143 знака, 15 слов)

Примеры языков и распознающих их конечных автоматов Пример 1. Язык: цепочки из 0 и 1, заканчивающиеся на 00 Например: 0010100, 0100, 000, . . .

Содержание слайда №8 (33 знака, 4 слова)

Операции над автоматами: тримминг

Содержание слайда №9 (419 знаков, 52 слова)

Полный конечный автомат Если переходы в автомате-распознавателе под воздействием некоторых событий не определены, то это означает, что соответствующие цепочки входного языка ошибочны, они не допускаются, не принадлежат языку, распознаваемому этим автоматом. Для любых манипуляций с автоматом это состояние нужно вводить явно. Полученный полный автомат с точки зрения распознавания языка эквивалентен исходному автомату.

Содержание слайда №10 (280 знаков, 34 слова)

Приведение конечного автомата Операция “приведения” (trimming) конечного автомата: выбрасывание всех состояний, недостижимых из начального состояния, и тех, из которых недостижимо ни одно из финальных состояний (не кодостижимых). При этом язык, допускаемый автоматом, не меняется!

Содержание слайда №11 (180 знаков, 26 слов)

Распознавание дополнения автоматного языка КА А распознает цепочку, если она переводит его из начального в одно из финальных состояний. Язык LA состоит из всех допускаемых цепочек.

Содержание слайда №12 (97 знаков, 10 слов)

Распознаватель дополнения автоматного языка 1: Заданный КА с неполностью определенными переходами

Содержание слайда №13 (82 знака, 7 слов)

Синхронная композиция двух автоматов-распознавателей Пересечение автоматных языков

Содержание слайда №14 (84 знака, 10 слов)

Синхронная композиция автоматов – два автомата, работающие синхронно от одного входа

Содержание слайда №15 (32 знака, 3 слова)

Синхронная композиция автоматов.

Содержание слайда №16 (277 знаков, 38 слов)

Пример. Статический анализ текста || программ Правильные цепочки событий обращения к буферу (запись, p от put и выборка, t от take) – язык (pt)* Анализ статического кода параллельной программы, работающей с буфером, может выявить любую неправильную подцепочку в потоке операций

Содержание слайда №17 (242 знака, 27 слов)

Синтез супервизоров – новая идея построения систем логического управления Автомат А может быть использован как супервизор – устройство управления, которое ограничивает функционирование системы процессов только правильными цепочками язык (pt)*

Содержание слайда №18 (270 знаков, 33 слова)

Синтез супервизоров - “горячая” область исследований INTERNATIONAL WORKSHOP ON DISCRETE EVENT SYSTEMS IEEE INT CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION CONFERENCE OF IEEE INDUSTRIAL ELECTRONICS IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION …

Содержание слайда №19 (46 знаков, 3 слова)

Эквивалентность двух автоматов-распознавателей

Содержание слайда №20 (178 знаков, 16 слов)

Эквивалентность двух конечных автоматов-распознавателей – как проверить? Определение. Два конечных автомата-распознавателя эквивалентны, если языки, распознаваемые ими, совпадают

Содержание слайда №21 (51 знак, 4 слова)

Эквивалентные автоматы-распознаватели. Теорема Мура

Содержание слайда №22 (37 знаков, 2 слова)

Эквивалентные автоматы-распознаватели

Содержание слайда №23 (46 знаков, 3 слова)

Минимизация конечных автоматов-распознавателей

Содержание слайда №24 (257 знаков, 30 слов)

Минимизация конечных автоматов-распознавателей Существует единственный (с точностью до изоморфизма, т. е. именования состояний) минимальный конечный автомат, распознающий данный автоматный язык. У КА есть его каноническое представление - это минимальный КА.

Содержание слайда №25 (149 знаков, 12 слов)

Пример неминимального автомата Подмножества состояний {0, 2}; {1, 5, 7}; {3, 6}; {4} – классы эквивалентных состояний. Как найти эту эквивалентность?

Содержание слайда №26 (386 знаков, 52 слова)

Минимизация конечных автоматов - распознавателей Построим на множестве состояний автомата А разбиения 0, 1, . . . , , такие, что в один класс k попадают состояния, из которых цепочки длиной k одновременно допускаются или одновременно не допускаются. Такие состояния будем считать k-эквивалентными, т. е. p k q (в отношении k) p k q  (*: = k) [ *(p, )F  *(q, )F ].

Содержание слайда №27 (171 знак, 11 слов)

Конечный автомат с эквивалентными состояниями 0 = {0, 1, 2, 5, 7}=A; {3, 4, 6}=B 1 = {0, 2}=C; {1, 5, 7}=D; {3, 6}=E; {4}=F 2 = {0, 2}; {1, 5, 7}; {3, 6}; {4} = 1 = 

Содержание слайда №28 (710 знаков, 101 слово)

Алгоритм построения эквивалентности  Так же, как и для автоматов-преобразователей, рассматриваем последовательность разбиений k на классы эквивалентности. Два состояния, s и q, k-эквивалентны, если под воздействием любой входной цепочки длиной не более k, автоматы попадают оба либо в пару финальных, либо в пару нефинальных состояний. 0 всегда состоит из двух классов: все нефинальные состояния – один класс, все финальные состояния – другой. Пусть уже построено разбиение k. Два состояния, находящиеся в одном классе эквивалентности k, будут в одном классе эквивалентности k+1 тогда и только тогда, когда для любого х состояния (s, x) и (q, x) будут в одном и том же классе предыдущего разбиения k.

Содержание слайда №29 (169 знаков, 9 слов)

Минимальный конечный автомат-распознаватель 0 = {0, 1, 2, 5, 7}=A; {3, 4, 6}=B 1 = {0, 2}=C; {1, 5, 7}=D; {3, 6}=E; {4}=F 2 = {0, 2}; {1, 5, 7}; {3, 6}; {4} = 1 = 

Содержание слайда №30 (251 знак, 34 слова)

Представление отношения эквивалентности матрицей Манипуляции с отношениями эквивалентности удобно выполнять с помощью матрицы инциденций, в которой в клетке ставим N, если элементы i и j НЕ принадлежат одному и тому же блоку соответствующего разбиения

Содержание слайда №31 (503 знака, 77 слов)

Эквивалентное представление алгоритма построения отношения эквивалентности Алгоритм: для каждой пары состояний (р, q) определяет, являются ли р и q эквивалентными Строим треугольную матрицу пар Начальное заполнение: для каждой пары (р, q), для которой одно состояние заключительное, другое - нет, ставим N (нет) Многократно: Для каждой пары , у которой не стоит N, проверяем, стоит ли N для пар хотя бы при одном х. Если стоит, то для пары ставим N. Алгоритм повторяется, пока добавляется хотя бы одно N

Содержание слайда №32 (52 знака, 3 слова)

Недетерминированные конечные автоматы-распознаватели

Содержание слайда №33 (272 знака, 31 слово)

Недетерминированные конечные автоматы-распознаватели Два начальных состояния, пустой переход, неоднозначный переход – как это понимать: как ошибки, коллизии? Что это за монстр? Что значит – несколько возможных переходов? Как его реализовывать? Автомат подбрасывает монету?

Содержание слайда №34 (235 знаков, 27 слов)

Основное правило для недетерминированных конечных автоматов-распознавателей Как понимать коллизии: а) несколько начальных состояний, б) несколько переходов, помеченных одним и тем же символом, в) переходы, помеченные пустым символом .

Содержание слайда №35 (37 знаков, 4 слова)

Как “работает” недетерминированный КА

Содержание слайда №36 (354 знака, 61 слово)

Формальное определение недетерминированного КА Формальное задание автомата примера: А=(S, , s0, , F) S=(s0, s1, s2, s3, s4);  = {a, b}; S0={s0, s2} (s0, a)={s4}; (s1, b)={s4}; (s2, a)={s4}; (s2, b)={s2, s3, s4); (s3, a)={s0, s1, s4};. . . ({s2, s3, s4}, a) ={s0, s1, s3, s4); Спонтанные переходы (s1, )={s1, s0}; (s3, )={s3, s2}; F={s3, s4}.

Содержание слайда №37 (33 знака, 5 слов)

Приведение к НДКА без -переходов

Содержание слайда №38 (70 знаков, 8 слов)

Чем удобны НДКА? Пример 1 Строим НЕдетерминированный конечный автомат:

Содержание слайда №39 (160 знаков, 24 слова)

Чем удобны НДКА? Пример 2 Задача: Построить КА с входным алфавитом  = {a, b, c}, распознающий все цепочки, которые начинаются символом а и кончаются символом с

Содержание слайда №40 (226 знаков, 28 слов)

Чем удобны НДКА? Пример 3 Задача: Построить КА с входным алфавитом  = {0, …, 9}, распознающий все числа, которые делятся на 25 (числа вводятся старшими разрядами вперед) Ясно, что это числа, заканчивающиеся на 00, 25, 50 и 75

Содержание слайда №41 (125 знаков, 12 слов)

Распознающая мощность недетерминированных КА Ясно, что детерминированные конечные автоматы – подкласс недетерминированных КА.

Содержание слайда №42 (44 знака, 4 слова)

Распознающая мощность недетерминированных КА

Содержание слайда №43 (77 знаков, 7 слов)

От недетерминированного автомата к эквивалентному детерминированному автомату

Содержание слайда №44 (37 знаков, 3 слова)

Минимизация алгоритмом “треугольника”

Содержание слайда №45 (78 знаков, 6 слов)

Минимизация построенного детерминированного автомата, эквивалентного исходному

Содержание слайда №46 (84 знака, 8 слов)

Пример перехода от недетерминированного автомата к эквивалентному детерминированному

Содержание слайда №47 (180 знаков, 25 слов)

Зачем нужны недетерминированные КА? Пример 2 Задача: Построить КА с входным алфавитом  = {a, b, c}, распознающий все цепочки, которые начинаются символом а и кончаются символом с.

Содержание слайда №48 (72 знака, 7 слов)

Операции над автоматными языками и конечными автоматами-распознавателями

Содержание слайда №50 (195 знаков, 29 слов)

Операции над автоматными языками Теорема. Если L1 и L2 – автоматные языки, то автоматными являются также их объединение L1L2, пересечение L1L2. конкатенация L1L2, дополнение -L1, итерация L1*

Содержание слайда №51 (98 знаков, 14 слов)

Операции над автоматами и автоматными языками, дающие в результате автоматные языки LA = LA1  LA2

Содержание слайда №52 (195 знаков, 24 слова)

Резюме: операции над автоматными языками Теорема. Множество автоматных языков замкнуто относительно операций: - дополнения, - объединения, - пересечения, - конкатенации, - итерции (звезда Клини).

Содержание слайда №53 (67 знаков, 7 слов)

Пример применения недетерминированных КА: Римская система счисления

Содержание слайда №54 (47 знаков, 7 слов)

Что написано на золотой медали Альфреда Нобиля?

Содержание слайда №55 (42 знака, 5 слов)

Зачем нужны недетерминированные КА? Пример

Содержание слайда №56 (896 знаков, 132 слова)

Правила построения римских чисел: Википедия Если меньшие цифры следуют за большими, то их значения суммируются. Только цифры, являющиеся степенью 10, могут повторяться до 3-х раз (т. е. V, L и D повторяться не могут), любые цифры могут отсутствовать. Меньшие цифры могут предшествовать большим. Значение числа получается вычитанием меньшей цифры из большей. Такое предшествование возможно в следующих случаях: меньшая цифра может быть только степенью 10 (т. е. C, X, I); ее значение может быть только либо одной пятой либо одной десятой значения большей (например, можно XL (=40) и XC (=90), но XM и XD – нельзя); она либо первая цифра в числе, либо ей предшествует цифра, значение которой, по крайней мере, в 10 раз больше ее значения (например, MXL(=1040) можно, LXL – нельзя); если за большей цифрой следует какая-либо цифра, она должна быть меньше, чем та, которая предшествует большей цифре.

Содержание слайда №57 (89 знаков, 11 слов)

Правила построения римских чисел: формально (1) Меньшие цифры обычно следуют за большими.

Содержание слайда №58 (231 знак, 33 слова)

Правила построения римских чисел: формально (2) Меньшие могут предшествовать большим. Меньшая цифра: может быть только степенью 10 (т. е. C, X, I); ее значение может быть только либо одной пятой либо одной десятой значения большей.

Содержание слайда №59 (291 знак, 42 слова)

Правила построения римских чисел: формально (3) Меньшая цифра либо первая в числе, либо ей предшествует цифра, значение которой, по крайней мере, в 10 раз больше ее значения. Если за большей цифрой следует какая-либо цифра, она должна быть меньше, чем та, которая предшествует большей цифре.

Содержание слайда №60 (32 знака, 4 слова)

Возможные значения римских чисел

Содержание слайда №61 (47 знаков, 5 слов)

Правила построения римских чисел: формально (4)

Содержание слайда №62 (769 знаков, 81 слово)

Недетерминированные автоматы: общее понимание Недетерминированные автоматы нельзя рассматривать, как физические устройства, которые читают входные символы, принимают решение, “угадывают”, в какое из состояний перейти, “обладают интуицией”, чтобы выбрать “правильный путь”, откуда-то “зная”, какими будут следующие символы входного слова (как в [1]). Недетерминированный автомат-распознаватель языка – это модель, математическая абстракция, абстрактное порождение мысли, ее бессмысленно реализовывать. С ней можно выполнять некоторые формальные операции: анализ, эквивалентные преобразования. По каждому недетерминированному автомату-распознавателю можно построить эквивалентный ему детерминированный автомат, а такой автомат можно реализовать и программно, и аппаратно.

Содержание слайда №63 (666 знаков, 70 слов)

Заключение Операции над КА-распознавателями: “trimming” – приведение, т. е. выбрасывание недостижимых и некодостижимых состояний в КА; по языку L, распознаваемому заданным КА, построение автомата, распознающего дополнение языка L, т. е. языка * - L; построение синхронной композиции двух КА-распознавателей = построение автомата, распознающего пересечение двух автоматных языков; проверка эквивалентности двух КА-распознавателей; минимизация КА-распознавателя; построение по недетерминированному КА эквивалентного детерминированного КА-распознавателя; построение КА, распознающего объединение и конкатенацию двух автоматных языков, заданных своими распознающими КА.

Содержание слайда №64 (806 знаков, 86 слов)

Заключение (2) Существует простой алгоритм проверки эквивалентности КА. Для такой проверки строится синхронная композиция автоматов. Синхронная композиция автоматов определяет пересечение двух автоматных языков. Конечные автоматы-распознаватели могут быть не минимальными. Алгоритм минимизации КА прост, он похож на алгоритм минимизации автоматов-преобразователей. Недетерминированный КА – это НЕ операционное устройство, которое действует, функционирует, принимая на вход цепочку. Это математическая модель, удобная для задания, для порождения языков. Недетерминизм КА не увеличивает возможностей распознавания языков: для любого недетерминированного КА существует эквивалентный ему детерминированный КА. Автоматные языки замкнуты относительно операций объединения, пересечения, конкатенации и дополнения.

Содержание слайда №65 (39 знаков, 6 слов)

Спасибо за внимание Спасибо за внимание

Содержание слайда №66 (46 знаков, 3 слова)

Эквивалентные автоматы-распознаватели: ПРИМЕРЫ

Содержание слайда №67 (237 знаков, 28 слов)

Эквивалентные автоматы-распознаватели. ПРИМЕР Все три автомата-распознавателя эквивалентны Они распознают один и тот же язык Третий пример показывает, что автомат с бесконечным числом состояний может быть эквивалентным конечному автомату