dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 27
Текст из файла (страница 27)
Попав в допускающее состояние автомата для R или S, можно поодному из ε-путей перейти в допускающее состояние нового автомата. Следовательно, язык автомата, представленного на рис. 3.17, а, равен L(R) U L(S).Выражение имеет вид RS для некоторых подвыражений R и S. Автомат для этойконкатенации представлен на рис. 3.17, б. Отметим, что начальное состояние первого автомата становится начальным состоянием для всего автомата, представляющегоконкатенацию, а допускающим для него будет допускающее состояние второго автомата.
Идея состоит в том, что путь, ведущий из начального в допускающее состояние, сначала проходит через автомат для R по некоторому пути, помеченномуцепочкой из L(R), а потом — через автомат для S по пути, помеченному цепочкой изL(S). Следовательно, путями автомата, представленного на рис. 3.17, б, будут те итолько те пути, которые помечены цепочками из языка L(R)L(S).Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, представленный на рис. 3.17, в.
Этот автомат позволяет пройти по следующим путям:3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 121121а) из начального состояния непосредственно в допускающее по пути, помеченному ε. Этот путь позволяет допустить цепочку ε, которая принадлежит L(R*)независимо от выражения R;б) перейти в начальное состояние автомата для R, пройти через этот автоматодин или несколько раз, и затем попасть в допускающее состояние. Этомножество путей дает возможность допускать цепочки, которые принадлежат языкам L(R), L(R)L(R), L(R)L(R)L(R) и так далее, порождая таким образом все цепочки из L(R*), за исключением, возможно, цепочки ε.
Но она получена в п. 3, а как отметка дуги непосредственно из начального в допускающее состояние.4.Выражение имеет вид (R) для некоторого подвыражения R. Автомат для R может быть автоматом и для (R), поскольку скобки не влияют на язык, задаваемыйвыражением.εεεεа)εб)εεεεв)Рис. 3.17. Индуктивный шаг преобразования регулярного выражения в ε-НКАЛегко заметить, что построенные автоматы удовлетворяют всем трем условиям индуктивной гипотезы: одно допускающее состояние, отсутствие дуг, ведущих в начальноесостояние, и дуг, выходящих из допускающего состояния.
122Стр. 122ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈПример 3.8. Преобразуем регулярное выражение (0 + 1)*1(0 + 1) в ε-НКА. Построим сначала автомат для 0 + 1. Для этого используем два автомата, построенные согласно рис. 3.16, в: один с меткой 0 на дуге, другой — с меткой 1. Эти автоматы соединены с помощью конструкции объединения (см. рис.
3.17, а). Результат изображенна рис. 3.18, а.εεεεа)εεεεεεεεб)εНачалоεεεεεεεεεεεεεв)Рис. 3.18. Автомат, построенный для примера 3.8Далее, применим к автомату (см. рис. 3.18, а) конструкцию итерации (см.рис. 3.17, в). Полученный автомат изображен на рис. 3.18, б. На последних двух шагах применяется конструкция конкатенации (см. рис. 3.17, б). Сначала автомат,представленный на рис. 3.18, б, соединяется с автоматом, допускающим только цепочку 1. Последний получается путем еще одного применения базисной конструк3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 123123ции (см. рис.
3.16, в) с меткой 1 на дуге. Отметим, что для распознавания цепочки 1необходимо создать новый автомат; здесь нельзя использовать автомат для 1, являющийся частью автомата, изображенного на рис. 3.18, а. Третьим автоматом в конкатенации будет еще один автомат для выражения 0 + 1. Опять-таки, необходимо создатькопию автомата (см. рис. 3.18, а), поскольку нельзя использовать автомат для 0 + 1,представляющий собой часть автомата (см.
рис. 3.18, б).Полный автомат показан на рис. 3.18, в. Заметим, что если удалить ε-переходы, тоэтот ε-НКА будет весьма похож на более простой автомат (см. рис. 3.15), также допускающий цепочки с 1 на предпоследней позиции. 3.2.4. Óïðàæíåíèÿ ê ðàçäåëó 3.23.2.1.ДКА представлен следующей таблицей переходов:01→ q1q2q1q2q3q1∗q3q3q2а) (∗) выпишите все регулярные выражения Rij( 0) . Замечание. Состояние qi можно рассматривать как состояние с целым номером i;б) (∗) выпишите все регулярные выражения Rij(1) .
Постарайтесь максимальноупростить эти выражения;в) выпишите все регулярные выражения Rij( 2) . Постарайтесь максимально упростить эти выражения;г) напишите регулярное выражение для языка заданного автомата;д) (∗) постройте диаграмму переходов для этого ДКА и напишите регулярноевыражение для его языка, исключив состояние q2.3.2.2.Повторите упражнение 3.2.1 для следующего ДКА.01→ q1q2q3q2q1q3∗q3q2q1Отметим, что решения для пунктов а, б и д непригодны в данном упражнении.3.2.3.124Стр.
124Преобразуйте следующий ДКА в регулярное выражение, используя технику исключения состояний из раздела 3.2.2.ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈ3.2.4.01→ ∗pspqpsrrqsqrПреобразуйте следующие регулярные выражения в НКА с ε-переходами;а) (∗) 01*;б) (0 + 1)01;в) 00(0 + 1)*.3.2.5.Исключите ε-переходы из НКА, полученных вами в упражнении 3.2.4. Решениедля пункта а можно найти на Web-страницах этой книги.3.2.6.(!) Пусть A = (Q, Σ, δ, q0, {qf}) — это такой ε-НКА, в котором нет переходов всостояние q0 и из состояния qf. Опишите язык, допускаемый каждой из следующих модификаций автомата А (в терминах языка L = L(A)):а) (∗) автомат, образованный по А путем добавления ε-перехода из qf в q0;б) (∗) автомат, построенный по А с помощью добавления ε-перехода из состояния q0 в каждое состояние, достижимое из q0 (по путям, метки которых могутсодержать как символы из Σ, так и ε);в) автомат, полученный по А посредством добавления ε-перехода в qf из каждого состояния, из которого по какому-либо пути достижимо qf;г) автомат, построенный по А путем одновременного выполнения пунктов б и в.3.2.7.(!!) Существует несколько упрощений конструкции теоремы 3.7, в которой регулярное выражение преобразовывалось в ε-НКА.
Вот три из них.1.Для оператора объединения вместо создания новых начального и допускающего состояний можно сгруппировать оба начальных состояния в одно,сохранив все их переходы. Аналогично, можно сгруппировать оба допускающих состояния в одно; к нему ведут все переходы, которые вели к каждому из исходных состояний.2.Для оператора конкатенации можно объединять допускающее состояниепервого автомата с начальным состоянием второго.3.Для оператора итерации можно просто добавить ε-переходы из допускающего состояния в начальное, и наоборот.В результате каждого из этих упрощений мы по-прежнему получаем правильную конструкцию, т.е. искомый ε-НКА, который для любого регулярного выра3.2.
ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 125125жения допускает язык этого выражения. Сочетание каких усовершенствований(1, 2 или 3) можно применить к этой конструкции, чтобы в результате получалсяправильный автомат для любого регулярного выражения?3.2.8.(∗!!) Постройте алгоритм, который по данному ДКА А вычисляет количествоцепочек длины n, допускаемых ДКА А (n не связано с количеством состоянийавтомата А).
Ваш алгоритм должен быть полиномиальным как относительно n,так и относительно количества состояний А. Указание. Используйте технику,предложенную в доказательстве теоремы 3.4.3.3. Ïðèìåíåíèå ðåãóëÿðíûõ âûðàæåíèéОсновным средством приложений для поиска образцов (образов, шаблонов) в текстеявляются регулярные выражения, задающие “схему” образца, который нужно распознать. Регулярные выражения компилируются в детерминированные или недетерминированные автоматы, которые затем моделируются для получения программы распознавания образов в тексте.
В этом разделе мы рассмотрим два важных класса приложений,основанных на регулярных выражениях: лексические анализаторы и поиск в тексте.3.3.1. Ðåãóëÿðíûå âûðàæåíèÿ â UNIXПрежде чем рассмотреть данные приложения, ознакомимся с системой обозначений,используемой в UNIX для расширенных регулярных выражений.
Эти обозначения предоставляют много дополнительных возможностей. На самом деле, расширения UNIXвключают некоторые особенности, в частности, возможность именовать и ссылаться напредыдущие цепочки, соответствующие шаблону, что, фактически, позволяет распознавать нерегулярные языки. Здесь эти особенности не рассматриваются, но вводятся сокращения, позволяющие записывать сложные регулярные выражения в сжатом виде.Первое усовершенствование в системе обозначений регулярных выражений связано стем, что большинство приложений работает с символами в коде ASCII. В наших примерах обычно использовался алфавит {0, 1}.
Наличие только двух символов позволяет использовать сокращенные выражения вроде 0 + 1 для обозначения “любого символа”. Однако если алфавит состоит, скажем, из 128 символов, то аналогичное выражение включало бы список всех этих символов и стало бы весьма неудобным для написания. Такимобразом, регулярные выражения в UNIX позволяют задавать классы символов для представления множеств символов в наиболее кратком виде.
Существуют следующие правила для классов символов.• Символ . (точка) обозначает “любой символ”.• Последовательность [a1a2…ak] обозначает регулярное выражениеa1 + a2 + … + ak126Стр. 126ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈТакое обозначение позволяет записывать примерно вдвое меньше символов, поскольку нет необходимости писать знак “+”. Например, четыре символа, используемые в операторах сравнения языка С, можно выразить в виде [<>=!].• В квадратных скобках записывается диапазон вида x–y для обозначения всехсимволов от x до y из последовательности символов в коде ASCII.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
