dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 22
Текст из файла (страница 22)
Тем самым доказаны равен∧∧ство δ E(q0, w) = δ D(qD, w) и индуктивная часть теоремы. 2.5.6. Óïðàæíåíèÿ ê ðàçäåëó 2.52.5.1. (∗) Рассмотрите следующий ε-НКА и:εabc∅{p}{q}{r}q{p}{q}{r}∅*r{q}{r}∅{p}→pа) найдите ε-замыкание каждого из состояний;б) выпишите все цепочки, длина которых не более 3, допустимые данным автоматом;в) преобразуйте данный автомат в ДКА.2.5.2.Выполните задание упражнения 2.5.1 со следующим ε-НКА.εabc{q, r}∅{q}{r}q∅{p}{r}{p, q}*r∅∅∅∅→p2.5.3.Постройте ε-НКА, которые допускают следующие языки. Для упрощения построений используйте, по возможности, ε-переходы:а) множество всех цепочек, состоящих из нуля или нескольких символов a, после которых стоит нуль или несколько символов b, и вслед за ними нуль илинесколько символов c;б) (!) множество цепочек, состоящих либо из повторяющихся один или несколько раз фрагментов 01, либо из повторяющихся один или несколько разфрагментов 010;2.5.
ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÝÏÑÈËÎÍ-ÏÅÐÅÕÎÄÀÌÈСтр. 9797в) (!) множество цепочек из 0 и 1, в которых хотя бы на одной из последних десяти позиций стоит 1.Ðåçþìå♦ Детерминированные конечные автоматы. ДКА имеет конечное число состоянийи конечное множество входных символов. Одно из состояний выделено как начальное, и нуль или несколько состояний являются допускающими. Функция переходов определяет, как изменяются состояния при обработке входных символов.♦ Диаграммы переходов.
Автомат удобно представлять в виде графа, в которомвершины соответствуют состояниям, а дуги, отмеченные входными символами,соответствуют переходам из состояния в состояние. Начальное состояние отмечается стрелкой, а допускающие состояния выделяются двойными кружками.♦ Язык автомата. Автомат допускает цепочки. Цепочка является допустимой, если,стартуя в начальном состоянии и обрабатывая символы этой цепочки по одному,автомат переходит в некоторое допускающее состояние. В терминах диаграммпереходов цепочка является допустимой, если она состоит из символов, отмечающих путь из начального состояния в одно из допускающих.♦ Недетерминированный конечный автомат. НКА отличается от ДКА тем, чтоНКА может иметь любое число переходов (в том числе, ни одного) из данного состояния в по данному входному символу.♦ Конструкция подмножеств. Множества состояний НКА можно рассматриватькак состояния некоторого ДКА.
Таким образом, мы можем преобразовать НКА вДКА, допускающий тот же самый язык.♦ ε-переходы. Можно расширить понятие НКА, разрешив переходы по пустой цепочке, т.е. вообще без входных символов. Расширенные таким образом НКА могут быть преобразованы в ДКА, допускающие те же самые языки.♦ Приложения типа “поиск в тексте”.
Недетерминированные конечные автоматыпредставляют собой удобный способ моделирования программы поиска одногоили нескольких ключевых слов в больших массивах текста. Эти автоматы либонепосредственно имитируются с помощью программы, либо вначале преобразуются в ДКА, а затем уже реализуются в виде программы.ËèòåðàòóðàПринято считать, что начало формальному изучению систем с конечным числом состояний было положено в работе [2]. Однако эта работа была посвящена не теперешнимДКА, а так называемой вычислительной модели “нейронных сетей”.
ДКА, в общеприня98Стр. 98ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛтом смысле слова, были введены независимо в нескольких различных вариантах в работах [1], [3] и [4]. Материал по недетерминированным автоматам и конструкции подмножеств взят из работы [5].1. D. A. Huffman, “The synthesis of sequential switching circuits”, J.Franklin Inst. 257:3–4(1954), pp. 161–190 and 275–303.2.W. S.
McCulloch and W. Pitts, “A logical calculus of the ideas immanent in nervuous activity”, Bull. Math. Biophysics 5 (1943), pp. 115–133. (Маккалок У.С., Питтс Э. Логическое исчисление идей, относящихся к нервной активности. / сб. “Автоматы”. —М.: ИЛ, 1956.
— С. 362–384.)3.G. H. Mealy, “A method for synthesizing sequential circuits”, Bell System TechnicalJournal 34:5 (1955), pp. 1045–1079.4.E. F. Moore, “Gedanken experiments on sequential machines”, in [6], pp. 129–153.(Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами.
/сб. “Автоматы”. — М.: ИЛ, 1956. — С. 179–210.)5.M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM J. Researchand Development 3:2 (1959), pp. 115–125. (Рабин М.О., Скотт Д. Конечные автоматыи задачи их разрешения. — Кибернетический сборник, вып.
4. — М.: ИЛ, 1962. —С. 56–71.)6.C. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956. (Шеннон К.Э., Мак-Карти Дж. Теория автоматов. / сб. “Автоматы”. — М.: ИЛ, 1956.)ËÈÒÅÐÀÒÓÐÀСтр. 9999100Стр. 100ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛÃËÀÂÀ 3Ðåãóëÿðíûåâûðàæåíèÿè ÿçûêèВ этой главе вводится система записи “регулярных выражений”.
Такие выражения представляют собой еще один способ определения языков, рассмотренный вкратце в разделе 1.1.2. Регулярные выражения можно рассматривать также как “язык программирования” для описания некоторых важных приложений, например, программ текстовогопоиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА имогут служить удобной альтернативой для описания программных компонентов.Определив регулярные выражения, покажем, что они могут задавать регулярные, итолько регулярные, языки. Обсудим также, каким образом регулярные выражения используются в различных системах программного обеспечения. Затем исследуем алгебраические законы для регулярных выражений.
Эти законы во многом подобны алгебраическим законам арифметики, однако между алгебрами регулярных и арифметическихвыражений есть и существенные различия.3.1. Ðåãóëÿðíûå âûðàæåíèÿПерейдем от “машинного” задания языков с помощью ДКА и НКА к алгебраическому описанию языков с помощью регулярных выражений. Установим, что регулярныевыражения определяют точно те же языки, что и различные типы автоматов, а именно,регулярные языки. В то же время, в отличие от автоматов, регулярные выражения позволяют определять допустимые цепочки декларативным способом.
Поэтому регулярныевыражения используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим два примера.Стр. 1011.Команды поиска, например, команда grep операционной системы UNIX или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерахили системах форматирования текста. В таких системах регулярные выражения используются для описания шаблонов, которые пользователь ищет в файле. Различныепоисковые системы преобразуют регулярное выражение либо в ДКА, либо в НКА иприменяют этот автомат к файлу, в котором производится поиск.2.Генераторы лексических анализаторов, такие как Lex или Flex. Напомним, что лексический анализатор — это компонент компилятора, разбивающий исходную про-грамму на логические единицы (лексемы), которые состоят из одного или нескольких символов и имеют определенный смысл. Примерами лексем являются ключевыеслова (например while), идентификаторы (любая буква, за которой следует нульили несколько букв и/или цифр) и такие знаки, как + или <=.
Генератор лексическиханализаторов получает формальные описания лексем, являющиеся по существу регулярными выражениями, и создает ДКА, который распознает, какая из лексем появляется на его входе.3.1.1. Îïåðàòîðû ðåãóëÿðíûõ âûðàæåíèéРегулярные выражения обозначают (задают, или представляют) языки. В качествепростого примера рассмотрим регулярное выражение 01*+10*. Оно определяет язык всехцепочек, состоящих либо из одного нуля, за которым следует любое количество единиц,либо из одной единицы, за которой следует произвольное количество нулей. В данныймомент мы не рассчитываем, что читатель знает, как интерпретируются регулярные выражения, поэтому наше утверждение о языке, задаваемом этим выражением, пока должно быть принято на веру.
Чтобы понять, почему наша интерпретация заданного регулярного выражения правильна, необходимо определить все использованные в этом выражении символы, поэтому вначале познакомимся со следующими тремя операциями надязыками, соответствующими операторам регулярных выражений1.Объединение двух языков L и M, обозначаемое L U M, — это множество цепочек, ко-1.торые содержатся либо в L, либо в М, либо в обоих языках. Например, если L = {001,10, 111} и M = {ε, 001}, то L U M = {ε, 10, 001, 111}.Конкатенация языков L и M — это множество цепочек, которые можно образоватьпутем дописывания к любой цепочке из L любой цепочки из М. Выше в разделе 1.5.2было дано определение конкатенации двух цепочек: результатом ее является записьодной цепочки вслед за другой. Конкатенация языков обозначается либо точкой, либо вообще никак не обозначается, хотя оператор конкатенации часто называют“точкой”.
Например, если L = {001, 10, 111} и M = {ε, 001}, то L.M, или простоLM, — это {001, 10, 111, 001001, 10001, 111001}. Первые три цепочки в LM — этоцепочки из L, соединенные с ε. Поскольку ε является единицей (нейтральным элементом) для операции конкатенации, результирующие цепочки будут такими же, каки цепочки из L. Последние же три цепочки в LM образованы путем соединения каждой цепочки из L со второй цепочкой из М, т.е. с 001. Например, 10 из L, соединенная с 001 из М, дает 10001 для LM.2.1Будем употреблять также термины “регулярные операции” и “регулярные операторы”, принятые в русскоязычной литературе.
— Прим. ред.102Стр. 102ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈИтерация (“звездочка”, или замыкание Клини2) языка L обозначается L* и представ-3.ляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из L. При этом допускаются повторения, т.е. однаи та же цепочка из L может быть выбрана для конкатенации более одного раза. Например, если L = {0, 1}, то L* — это все цепочки, состоящие из нулей и единиц. ЕслиL = {0, 11}, то в L* входят цепочки из нулей и единиц, содержащие четное количество единиц, например, цепочки 011, 11110 или ε, и не входят цепочки 01011 или 101.Более формально язык L* можно представить как бесконечное объединение Ui≥0 Li,где L0 = {ε}, L1 = L и Li для i > 1 равен LL…L (конкатенация i копий L).Пример 3.1. Поскольку идея итерации языка может показаться довольно сложной,рассмотрим несколько примеров.
Для начала возьмем L = {0, 11}. L0 = {ε} независимо отязыка L; нулевая степень означает выбор нулевого количества цепочек из языка L. L1 = L,что означает выбор одной цепочки из L. Таким образом, первые два члена в разложенииL* дают {ε, 0, 11}.Далее рассмотрим L2. Выберем две цепочки из L и, поскольку их можно выбирать сповторениями, получим четыре варианта, которые дают L2 = {00, 011, 110, 1111}. Аналогично, L3 представляет собой множество цепочек, образованных троекратным выборомиз двух цепочек языка L. Следовательно, L3 имеет вид{000, 0011, 0110, 1100, 01111, 11011, 11110, 111111}Для вычисления L* необходимо вычислить Li для каждого i и объединить все эти языки. Язык Li содержит 2i элементов.
Хотя каждое множество Li конечно, объединение бесконечного числа множеств Li образует, как правило, бесконечный язык, что справедливо,в частности, и для нашего примера.Пусть теперь L — множество всех цепочек, состоящих из нулей. Заметим, что такойязык бесконечен, в отличие от предыдущего примера, где был рассмотрен конечныйязык. Однако нетрудно увидеть, что представляет собой L*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
