Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 16

Определим б индукцией по длине входной цепочки следующим образом. Базис. 6(д, е) =а, т.е., находясь в состоянии д и не читая вход, мы остаемся в со- стоянии д. Индукции. Пусть в — цепочка вида ха, т.е. а — последний символ в цепочке, а х— цепочка, состоящая из всех символов цепочки ч, за исключением последнего. Наприз мер, и =! 101 разбивается на х = 110 и а = 1. Тогда б (Ч, ) = Ю(Ю (Ч, ), а) (2.1) Выражение (2.1) может показаться довольно громоздким, но его идея проста.

Для того чтобы найти Ю (д, зе), мы вначале находим 6 (а, х) — состояние, в которое автомат попадает, обработав все символы цепочки м, кроме последнего. Предположим, что это состояние р, т.е. 6 (д, х) = р. Тогда 6 (д, м) — это состояние, в которое автомат перехо- дит изр при чтении а — последнего символа зг. Таким образом, 6 (д, и) = б(р, а). Пример 2.4.

Построим ДКА, допустимым для которого является язык 2. = (н ! зг содержит четное число О и четное число 1). Вполне естественно, что состояния данного ДКА используются для подсчета числа нулей и единиц. При этом подсчет ведется по модулю 2, т.е. состояния "запоминают*', четное или нечетное число О или 1 было прочитано на данный момент. Итак, существуют четыре состояния, которые можно описать следующим образом. дв '. Прочитано четное число О и четное число 1.

д1 . Прочитано четное число О и нечетное число 1. д,: Прочитано четное число 1 и нечетное число О. Оз . Прочитано нечетное число О и нечетное число 1. Состояние дв одновременно является и начальным, и единственным допускающим. Начальным оно является потому, что до того, как будут прочитаны какие-либо входные данные, количество прочитанных и О, и 1 равно нулю, а нуль — число четное. Это же со- ' Напомним, что мы условились обозначать символы буквами из начальной части алфавита, а цепочки — буквами из конца алфавита Это соглашение необходимо для того, чтобы понять смысл выражения "цепочка вила ха".

ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ стояние — единственное допускающее, поскольку в точности описывает условие принадлежности последовательности из 0 и 1 языку Т.. Теперь мы знаем почти все, что нужно для определения ДКА, соответствующего языку 1,. Это автомат г( = ((4)о, Чь й, Чз), (О, 1), б, Чо, (Чо)) где функция переходов б изображается диаграммой переходов на рис.2.6.

Заметим, что по каждому символу 0 совершается переход через горизонтальную пунктирную линию. Таким образом, после чтения четного числа символов 0 мы находимся над горизонтальной линией, в состоянии е)о или дь а после нечетного числа — под ней, в состоянии д, или В. Аналогично, символ 1 заставляет нас пересечь вертикальную пунктирную линию. Следовательно, после чтения четного числа единиц мы находимся слева от веРтикальной линии, в состоЯнии до или е)з, а после чтениЯ нечетного — спРава, в состоянии о, или дз. Эти наблюдения представляют собой нестрогое доказательство того, что данные четыре состояния интерпретируются правильно.

Хотя можно и формально, как в примере 1.23, доказать корректность наших утверждений о состояниях, используя совместную индукцию. Начало Рис. 2.б. Диаграмма переходов дяя ДКА из примера 24 Данный ДКА можно также представить таблицей переходов, изображенной на рнс. 2.7. Но нам нужно не просто построить ДКА. Мы хотим с его помощью показать, как строится функция б по функции переходов б. Допустим, на вход подается цепочка 110101.

Она содержит четное число 0 и 1, поэтому принадлежит данному языку. Таким образом, мы ожидаем, что б (д„!10101) = еуо, так как до — единственное допускающее состояние. Проверим это утверждение. Для проверки требуется найти б (о!о, н) для всех постепенно нарастающих, начи- ная с к, префиксов н цепочки 110101. Результат этих вычислений выглядит следующим образом. 2.2. ДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ Рис. 2.7 Таблица переходов для ДКА из примера 2А ° 6 (зуе, е) = 9о. ° 6 Ие, 1) = б (6 Йо, е), 1) = б (зуо, 1) = зу1 б (зуо 11) = 6 (6 (0о, 1), 1) = б (0п 1) = 0о б (суе, 11О) = 6 ( б (ае, 11) О) = б (суо, О) = аз б (уо, 1101) = 6(6 (зуо, 110), 1) = 6 (зуз, 1) = зуз б (еуо, 11010) = 6 ( 6 (еуо, 1101), О) = б (аз, О) = зу~ ° б (ао, 110101) = б ( б (зуо, 11010), 1) = б (ап ! ) = еуо П Стандартные обозначения и локальные переменные По прочтении этого раздела может сложиться впечатление, что нужно обязательно пользоваться введенными здесь обозначениями, т.е.

функцию переходов обозначать 6, ДКА — буквой А и т.д. Действительно, во всех примерах мы стараемся использовать одинаковые переменные для обозначения однотипных объектов. Делается это для того, чтобы легче было вспомнить, о каком типе переменных идет речь. Так, в программах У почти всегда обозначает переменную целого типа. Однако в выборе обозначений для компонентов автомата (или чего-либо другого) мы совершенно свободны. Например, при желании мы можем обозначить ДКА буквой М, а его функцию переходов — буквой Т.

Более того, нет ничего странного в том, что одна и та же переменная обозначает, в зависимости от контекста, разные объекты. Например, функции переходов в примерах 2.1 и 2лй обозначены буквой б. Но эти две функции являются локальными переменными и относятся только к своим примерам. Они значительно отличаются друг от друга и никак не связаны.

2.2.5. Язык ДКА Теперь можно определить язык ДКА вида А = (Д, Х, 6, зуе, Р). Этот язык обозначается У,(А) и определяется как ГЛАНА 2. КОНЕЧНЫЕ АВТОМАТЫ з.(А) = ( зи ) б (ды зи) принадлежит г") . Таким образом, язык — множество цепочек, приводящих автомат из состояния з)и в одно нз допускающих состояний. Если язык з'.

есть ЦА) для некоторого ДКА А, то говорят, что з. является регулярззым языком. Пример 2.5. Ранее упоминалось, что если А — ДКА из примера 2.1, то ((А) — множество цепочек из 0 и 1, содержащих подцепочку 01. Если же А — ДКА из примера 2Ач то ЦА) — множество всех цепочек из 0 н 1, содержащих четное число 0 и четное число 1. С2 2.2.6.

Упражнения к разделу 2.2 2.2.1. На рис. 2.8 изображена игра "катящиеся шарики". Мраморный шарик бросается в точке А илн В. Направляющие рычаги хп хз и хз заставляют шарик катиться влево или вправо. После того как шарик, столкнувшись с рычагом, проходит его, рычаг поворачивается в противоположную сторону, так что следующий шарик покатится уже в другую сторону. Рис. 2.8.

Игра "катящиеся шарики" Выполните следующее: а) (а) постройте конечный автомат, моделирующий данную игру. Пусть А и В обозначают входы — те места, купа бросается шарик. Допустимость соответствует попаданию шарика в точку гз, а недопустимость — в точку С; б) (1) лайте нестрогое описание этого автомата; в) прелположим, что рычаги поворачиваются до того, как шарик проходит через них.

Как это обстоятельство повлияет на ответ в частях (а) и (б)? 2.2. ДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 69 (я!) Мы определяли б, разбивая цепочку на цепочку и слелующий за ней символ (в индуктивной части определения, уравнение 2.1). Однако неформально б представляется как описание событий вдоль пути с определенной цепочкой отметок переходов. Поэтому не должно иметь значения, как именно разбивать входную цепочку в определении б. Покажите, что в действительности б (ч, ху) = б (б (г7, х),у) для всякого состояния д и цепочек х и у, Указание. Проведите индукцию по (у1 (!) Покажите, что б (гу, ах) = б ( б (д, а), х) для всякого состояния су, цепочки х и входного символа а.

Указание. Используйте упражнение 2.2.2. 2.2.2. 2.2.3. 2.2.4. Опишите ДКА, которые допускают следующие языки над алфавитом (О, 1): а) (я) множество всех цепочек, оканчивающихся на 00; б) множество всех цепочек, содержащих три нуля подряд; в) множество цепочек, содержащих в качестве надцепочки 011. 2.2.5. (!) Опишите ДКА, допускающие такие языки над алфавитом (О, 1): а) множество всех цепочек, в которых всякая подцепочка из пяти последовательных символов содержит хотя бы два 0; б) множество всех цепочек, у которых на десятой позиции справа стоит 1; в) множество цепочек, которые начинаются или оканчиваются (или и то, и другое) последовательностью О1; а) (я) множество всех цепочек, начинающихся с 1, и если рассматривать их как двоичное представление целого числа, то это число кратно 5.

Например, цепочки 101, 1010 и 1111 принадлежат этому языку, а цепочки О,!00 и 111 — нет; б) множество всех цепочек„запись которых в обратном порядке образует двоичное представление целого числа, кратного 5. Примерами цепочек этого языка являются цепочки О, 10011, 1001100 и 0101.

Пусть А есть некоторый ДКА и д — его состояние, у которого б(д, а) = д для любого символа ввода а. Докажите индукцией по длине входной цепочки н, что б (и. н) = г7 для всякой входной цепочки н. 2.2.8. Пусть А — некоторый ДКА и а — входной символ, причем фд, а) = д для всех состояний д автомата А: 70 ГЛАВА 2.

КОНЕЧНЫЕ АВТОМАТЫ г) множество цепочек, в которых число нулей делится на пять, а число единиц — на три. 2.2.6. (!!) Опишите ДКА, которые допускают следующие языки над алфавитом (О, 1): а) докажите индукцией по л, что б(д, а") =лдпя всякого л> О„где а" — цепочка, состоящая из и символов гб б) покажите, чтолибо (а) ~ЦА),либо (а) Пь(А) =И. 2.2.9. (ь!) Пусть А = Я, Е, б, пм (сг)) — ДКА. Предположим, что для всех а из Х имеет место равенство б(до, а) = б(Оя л): а) покажите, что для всех и «аверно равенство б (до, и) = б (дь а); б) покажите, что если х — непустая цепочка из ЦА), то для всех й > О, х (т.е. цепочках, записанная 1г раз) также принадлежит ЦА). 2,2ЛО.

(ч)) Рассмотрим ДКА со следующей таблицей переходов: Опишите неформально язык, допустимый данным ДКА, и докажите индукцией по длине входной цепочки, что ваше описание корректно. Указание. Устанавливая индуктивную гипотезу, разумно сформулировать утверждение о том, какие входные последовательности приводят в каждое состояние, а не только в допускающее. 2.2.11. (!) Выполните задание упражнения 2.2АО со следующей таблицей переходов.

2.3. Недетерминированные конечные автоматы "Недетерминированный" конечный автомат, или НКА (ЯРА — Хопдегеппишйзпс Р(ште Ашошагоп), обладает свойством находиться в нескольких состояниях одновременно. Эту особенность часто представляют как свойство автомата делать "догадки" относительно его входных данных. Так, если автомат используется для поиска определенных цепочек символов (например, ключевых слов) в текстовой строке большой длины, то в начале поиска полезно "догадаться", что мы находимся в начале одной из этих цепочек, а затем использовать некоторую последовательность состояний для простой проверки того, что символ за символом появляется данная цепочка. Пример приложения такого типа приведен в разделе 2.4. 2.3.

НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 71 Прежде, чем перейти к приложениям, нужно определить недетерминированные конечные автомать| и показать, что всякий такой автомат допускает язык, допустимый некоторым ДКА, т.е. НКА допускают регулярные языки точно так же, как и ДКА. Однако есть причины рассматривать и НКА. Они зачастую более компактны и легче строятся, чем ДКА. Кроме того, хотя НКА всегда можно преобразовать в ДКА, последний может иметь экспоненциально больше состояний, чем НКА. К счастью, такие случаи довольно редки. 2.3.1.

Неформальное описание недетерминированного конечного автомата НКА, как и ДКА, имеют конечное множество состояний, конечное множество входных символов, одно начальное состояние и множество допускающих состояний. Есть также функция переходов, которая, как обычно, обозначается через б, Различие между ДКА и НКА состоит в типе функции 6 В НКА Б есть функция, аргументами которой являются состояние и входной символ (как и в ДКА), а значением — множество, состояшее из нуля, одного или нескольких состояний (а не одно состояние, как в ДКА). Прежде чем дать строгое определение НКА, рассмотрим пример.