dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 16
Текст из файла (страница 16)
2.8 изображена игра “катящиеся шарики”. Мраморный шарик бросаетсяв точке A или B. Направляющие рычаги x1, x2 и x3 заставляют шарик катитьсявлево или вправо. После того как шарик, столкнувшись с рычагом, проходитего, рычаг поворачивается в противоположную сторону, так что следующий шарик покатится уже в другую сторону.Рис. 2.8. Игра “катящиеся шарики”Выполните следующее:а)(∗) постройте конечный автомат, моделирующий данную игру. Пусть A иB обозначают входы — те места, куда бросается шарик. Допустимость соответствует попаданию шарика в точку D, а недопустимость — в точку C;б)(!) дайте нестрогое описание этого автомата;в)предположим, что рычаги поворачиваются до того, как шарик проходитчерез них.
Как это обстоятельство повлияет на ответ в частях (а) и (б)?2.2. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 6969∧2.2.2.(∗!) Мы определяли δ , разбивая цепочку на цепочку и следующий за ней символ (в индуктивной части определения, уравнение 2.1). Однако неформально∧δ представляется как описание событий вдоль пути с определенной цепочкойотметок переходов. Поэтому не должно иметь значения, как именно разбивать∧входную цепочку в определении δ . Покажите, что в действительности∧∧∧δ (q, xy) = δ ( δ (q, x), y) для всякого состояния q и цепочек x и y. Указание.Проведите индукцию по |y|.∧∧∧2.2.3.(!) Покажите, что δ (q, ax) = δ ( δ (q, a), x) для всякого состояния q, цепочки x ивходного символа a.
Указание. Используйте упражнение 2.2.2.2.2.4.Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}:а) (∗) множество всех цепочек, оканчивающихся на 00;б) множество всех цепочек, содержащих три нуля подряд;в) множество цепочек, содержащих в качестве подцепочки 011.2.2.5.(!) Опишите ДКА, допускающие такие языки над алфавитом {0, 1}:а) множество всех цепочек, в которых всякая подцепочка из пяти последовательных символов содержит хотя бы два 0;б) множество всех цепочек, у которых на десятой позиции справа стоит 1;в) множество цепочек, которые начинаются или оканчиваются (или и то, и другое) последовательностью 01;г) множество цепочек, в которых число нулей делится на пять, а число единиц — на три.2.2.6.(!!) Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}:а) (∗) множество всех цепочек, начинающихся с 1, и если рассматривать их как двоичное представление целого числа, то это число кратно 5.
Например, цепочки101, 1010 и 1111 принадлежат этому языку, а цепочки 0, 100 и 111 — нет;б) множество всех цепочек, запись которых в обратном порядке образует двоичное представление целого числа, кратного 5. Примерами цепочек этогоязыка являются цепочки 0, 10011, 1001100 и 0101.2.2.7.Пусть A есть некоторый ДКА и q — его состояние, у которого δ(q, a) = q длялюбого символа ввода a.
Докажите индукцией по длине входной цепочки w, что∧δ (q, w) = q для всякой входной цепочки w.2.2.8.70Стр. 70Пусть A — некоторый ДКА и a — входной символ, причем δ(q, a) = q для всехсостояний q автомата A:ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ∧а) докажите индукцией по n, что δ (q, an) = q для всякого n ≥ 0, где an — цепочка, состоящая из n символов a;б) покажите, что либо {a}* ⊆ L(A), либо {a}* I L(A) = ∅.2.2.9.(∗!) Пусть A = (Q, Σ, δ, q0, {qf}) — ДКА. Предположим, что для всех a из Σ имеет место равенство δ(q0, a) = δ(qf, a):∧∧а) покажите, что для всех w ≠ ε верно равенство δ (q0, w) = δ (qf, a);б) покажите, что если x — непустая цепочка из L(A), то для всех k > 0, xk (т.е.цепочка x, записанная k раз) также принадлежит L(A).2.2.10. (∗!) Рассмотрим ДКА со следующей таблицей переходов:01→AAB*BBAОпишите неформально язык, допустимый данным ДКА, и докажите индукцией по длине входной цепочки, что ваше описание корректно. Указание.
Устанавливая индуктивную гипотезу, разумно сформулировать утверждение о том,какие входные последовательности приводят в каждое состояние, а не тольков допускающее.2.2.11. (!) Выполните задание упражнения 2.2.10 со следующей таблицей переходов.01→*ABA*BCACCC2.3. Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû“Недетерминированный” конечный автомат, или НКА (NFA — Nondeterministic FiniteAutomaton), обладает свойством находиться в нескольких состояниях одновременно.
Этуособенность часто представляют как свойство автомата делать “догадки” относительноего входных данных. Так, если автомат используется для поиска определенных цепочексимволов (например, ключевых слов) в текстовой строке большой длины, то в началепоиска полезно “догадаться”, что мы находимся в начале одной из этих цепочек, а затемиспользовать некоторую последовательность состояний для простой проверки того, чтосимвол за символом появляется данная цепочка. Пример приложения такого типа приведен в разделе 2.4.2.3.
ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 7171Прежде, чем перейти к приложениям, нужно определить недетерминированные конечные автоматы и показать, что всякий такой автомат допускает язык, допустимый некоторым ДКА, т.е. НКА допускают регулярные языки точно так же, как и ДКА. Однако естьпричины рассматривать и НКА. Они зачастую более компактны и легче строятся, чем ДКА.Кроме того, хотя НКА всегда можно преобразовать в ДКА, последний может иметь экспоненциально больше состояний, чем НКА.
К счастью, такие случаи довольно редки.2.3.1. Íåôîðìàëüíîå îïèñàíèå íåäåòåðìèíèðîâàííîãîêîíå÷íîãî àâòîìàòàНКА, как и ДКА, имеют конечное множество состояний, конечное множество входных символов, одно начальное состояние и множество допускающих состояний. Естьтакже функция переходов, которая, как обычно, обозначается через δ. Различие междуДКА и НКА состоит в типе функции δ. В НКА δ есть функция, аргументами которой являются состояние и входной символ (как и в ДКА), а значением — множество, состоящее из нуля, одного или нескольких состояний (а не одно состояние, как в ДКА).
Преждечем дать строгое определение НКА, рассмотрим пример.Пример 2.6. На рис. 2.9 изображен недетерминированный конечный автомат, допускающий те и только те цепочки из 0 и 1, которые оканчиваются на 01. Начальным является состояние q0, и можно считать, что автомат находится в этом состоянии (а также,возможно, и в других состояниях) до тех пор, пока не “догадается”, что на входе началась замыкающая подцепочка 01. Всегда существует вероятность того, что следующийсимвол не является начальным для замыкающей подцепочки 01, даже если это символ 0.Поэтому состояние q0 может иметь переходы в себя как по 1, так и по 0.НачалоРис. 2.9. НКА, допускающий цепочки, которые оканчиваются на 01Если очередной входной символ — 0, то НКА может предположить, что уже началасьзамыкающая подпоследовательность 01.
Таким образом, дуга с меткой 0 ведет из состояния q0 в q1. Заметим, что из q0 выходят две дуги, отмеченные символом 0. НКА может перейти как в q0, так и в q1, и в действительности переходит в оба эти состояния. Мыубедимся в этом, когда дадим строгое определение НКА. В состоянии q1 наш НКА проверяет, является ли следующий входной символ единицей. Если это так, то он переходитв состояние q2 и считает цепочку допустимой.Заметим, что из состояния q1 дуга, отмеченная нулем, не выходит, а состояние q2 вообще не имеет выходящих дуг. В этих состояниях пути НКА “умирают”, хотя другие пути попрежнему существуют.
В то время как ДКА имеет в каждом состоянии ровно одну выхо72Стр. 72ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛдящую дугу для каждого входного символа, для НКА такого ограничения нет. На примерерис. 2.9 мы убедились, что числом дуг может быть, например, нуль, один или два.На рис. 2.10 видно, как НКА обрабатывает цепочку. Показано, что происходит, когдаавтомат (см.
рис. 2.9) получает на вход последовательность 00101. Движение начинаетсяиз единственного начального состояния q0. Когда прочитан первый символ 0, НКА может перейти в состояние либо q0, либо q1, а потому переходит в оба эти состояния. Этидва пути представлены на рис. 2.10 вторым столбцом.(тупик)(тупик)Рис. 2.10. Состояния, в которых находится НКА в процессе обработки цепочки 00101Затем читается второй символ 0. Из состояния q0 вновь можно перейти в q0 и q1. Однако состояние q1 не имеет переходов по символу 0, и поэтому оно “умирает”.
Когда появляется третий входной символ, 1, нужно рассмотреть переходы из обоих состояний q0и q1. Из состояния q0 по 1 есть переход только в q0, а из q1 — только в q2. Таким образом,прочитав цепочку 001, НКА находится в состояниях q0 и q2.
НКА допускает ее, поскольку q2 — допускающее состояние.Однако чтение входных данных еще не завершено. Четвертый входной символ 0 приводит к тому, что ветвь, соответствующая q2, отмирает, в то время как q0 переходит в q0 иq1. По последнему символу 1 происходит переход из q0 в q0, а из q1 — в q2. Поскольку мывновь попали в допускающее состояние, то цепочка 00101 допустима. 2.3.2. Îïðåäåëåíèå íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòàТеперь мы определим формально понятия, связанные с недетерминированными конечными автоматами, выделив по ходу различия между ДКА и НКА. Структура НКА восновном повторяет структуру ДКА:A = (Q, Σ, δ, q0, F).Эти обозначения имеют следующий смысл.1.Q есть конечное множество состояний.2.Σ есть конечное множество входных символов.3.q0, один из элементов Q, — начальное состояние.4.F, подмножество Q, — множество заключительных (или допускающих) состояний.2.3.
ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 73735.δ, функция переходов, — это функция, аргументами которой являются состояние из Qи входной символ из Σ, а значением — некоторое подмножество множества Q. Заметим, что единственное различие между НКА и ДКА состоит в типе значений функцииδ. Для НКА — это множество состояний, а для ДКА — одиночное состояние.Пример 2.7. НКА на рис.
2.9 можно формально задать, как({q0, q1, q2}, {0, 1}, δ, q0, {q2}),где функция переходов δ задается таблицей на рис. 2.11. 01{q2, q1}{q0}q1∅{q2}*q2∅∅→q0Рис. 2.11. Таблица переходов для ДКА, допускающего цепочки, которые оканчиваются на 01Заметим, что, как и для ДКА, функцию переходов НКА можно задавать таблицей.Единственное различие состоит в том, что в таблице для НКА на пересечениях строк истолбцов стоят множества, хотя, возможно, и одноэлементные, т.е. содержащие одинэлемент (singleton). Заметим также, что, когда из некоторого состояния по определенному символу перехода нет, на пересечении соответствующих строки и столбца должностоять ∅ — пустое множество.2.3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
