Формальные языки и автоматы - Методичка для сдающих и пересдающих, страница 2

Жара продолжается: теперь надо вычислить ()- множество символов,которые могут идти прямо после цепочки, порожденной поддеревом.Здесь строгие алгоритмы выглядят еще скучнее, чем для прошлых множеств, но метод пристального взгляда по-прежнему здесь справляется довольно неплохо (хотяиногда и допускает ошибки: мой вот пристальный взгляд в свое время накосячил, атеперь я пишу эту методичку).12Но в любом случае, вот алгоритм: ∙ : для каждого ∈ () добавить () в ()Для *: для каждой позиции ∈ () добавить ()в ()ДляЕсли первое правило вполне понятно, то второе уже посложнее. Оно становится по-* может получиться цепочка .

Тогда все встаетна свои места (потому что явным образом видно, что за всеми () спокойномогут идти любые символы из (). Осозновая это, вы, наверное, не накося-нятнее, если напомнить себе, что изчите так, как однажды это сделал я.Для нашего дерева получается такая таблица: ()1{2, 3, 8}2{2, 3, 8}3{4}4{2, 3, 8}5{6}6{7}7{8}8{}6. Строим таблицу переходов. Состояния здесь описываются множествами, как и впрошлой главе. За начальное состояние берется множество (корень дерева).Дальше правила переходов описываются следующим образом:(, ) =⋃︀ ()=∩Сложная формула, за которой хрен пойми какая логика стоит, поэтому рассмотримна живом примере:В данном случае наше стартовое состояние = {1, 5}.

= {2, 4, 5, 6}(множество цифр, которые в пронумерованном РВ стоят подсимволом )Пересекая множества и получим {5}. (5) смотрим по таблице - {6}. Такого множества в качестве состояния у нас еще не было, поэтому назовем его = {6}.Таким образом получается, что (, ) = .СимволАбсолютно аналогично поступаем со всеми символами алфавита и всеми неописанными множествами. Со временем новые состояния перестанут поступать, а мы получимзаконченную таблицу.Конечным состоянием объявляется то, которое в своем множестве содержит номерсимвола конца.13(|) * | получается{2, 4, 5, 6} {1, 3, 7}{1, 5}{6}x*{2, 3, 8}{7}x{4}x* {8}xxДля нашегоследующая таблица:Осталось всего ничего: построить сам ДКА по таблице3.2Почему это работаетПо сути каждое состояние описано множеством тех номеров букв, которые могут насиз этого состояния вывести.

Действительно, если внимательно посмотреть на нашеРВ,((|) * |)#1 2 34567 81 -можно заметить, что выйти из начального состояния мы можем только по буквами5.При этом те же буквы, но с другими номерами нам не подойдут.ы здесь тоже появляются вполне по делу: через них очень удобно описываются теномера букв, которые выводят нас из состояния, в котором мы оказались. Ведь еслимы уже прошли вперед по символупо определению сможем встретить1, то дальше в цепочке, удовлетворящей РВ, мытолько символ из (1).Из всех этих номеров можно построить очень простой, но здоровый автомат разбора,где алфавит нетерминалов будет состоять из чисел, которыми нумеруются буквы висходном РВ.

Просто этот большой автомат потом можно будет сократить, заменивномера, на буквы, которые им соответствуют.14Глава 4Минимизация ДКАНедоумевающий читатель мог задаться вопросом: как же так получилось, что мывзяли одно РВ, и получилось 2 разных ДКА? И почему это второй ДКА получилсятаким аккуратным?А все потому, что ДКА из НКА мы не минимизировали.4.1Алгоритм1. Первым делом автомат надо дополнить, то есть, сделать так, чтобы в нем всегдабыло куда перейти (сделаем так, чтобы не было правил вида(, ) = Ø)Если автомат уже полный, то ничего не делаем, в противном случае добавляем новоесостояние(ну или как вы его назовете, я называю, потому что это(и из в себя же поот словаудобно), а после этого ведете в него все отсутствующие дугивсем буквам алфавита).В качестве примера возьмем нашего старого доброго уродца из "НКА по РВ"и дополним его:152.

Строим разбиение0 = { }, { ∖ },0гдемножеств состояний следующим образом:{ }- все конечные состояния, а{ ∖ }- все остальные. Вдальнейшем эти множества я буду называть группами.А дальше строится разбиениеЕслии1следующим образом:принадлежает одной группе и по всем нетерминальным символам пере-ходят в одну и ту же группу (не обязательно в свою), то они остаются в одной группе.А если есть два состояния из одной группы, и по какому-то нетерминалу переходитв другую группу, то он уходит в новую группу.И вот все эти разбиения надо продолжать до тех пор, пока не окажется, что = +1(умные люди называют это стабилизацией).Рассмотрим отдельный пример:0 = {}, {, , , }, при этом , по символу переходят в {}, а по - в своюгруппу. , же по , переходят в свою группу.

И тут можно сначала выделитьотдельную группу {}, а потом еще одну группу {}. На самом деле группа определяется тем, что ее элементы ведут себя одинаково, а в данном случае и ведутсебя идентично, поэтому правильнее будет выделить их вместе в отдельную группуи получить разбиение1 = {}, {, }, {, }. Если вдруг выяснится, что и насамом деле ведут себя по-разному, то на следующих итерациях, они будут разведеныпо разным группам, но пока что они должны быть в одной группе.

За такими удалениями разных элементов в одну группу надо внимательно следить, иначе можнополучить ошибочный ответ.А теперь мы построим разбиения на группы для нашего дополненного автомата:При этом у каждой группы я буду ставить ее порядковый номер, а возле состоянийв группе буду ставить "вектор переходов в группы". Поясню за сложное словосочетание "вектор переходов в группы":группу-0, а по03означает, что помы переходим изв- в группу-3. Так сразу становится понятно, кого надо разнести поразным группам, а кого надо оставить в одной.01234= {01 , 11 , 01 , 01 }0 , {, , , , }1= {, , }0 , {}1 , {20 , 22 , 21 , 02 , 22 }2= {, , }0 , {}1 , {}2 , {43 , 33 }3 , {}4 , {}5= {05 , 05 , 05 }0 , {66 }1 , {30 }2 , {46 }3 , {61 }4 , {06 }5 , {66 }6= 3 : закончили16Опешивший читатель может подумать, что я охерел и не всегда выставлял "векторпереходов в группы" у состояний.

Это все банально потому, что мне очень лень. Необязательно на одной итерации разносить по разным группам ВСЕ, что только можно. Если в одной группе есть два состояния, которые надо разнести по группам, торано или поздно мы все равно до них доберемся и разнесем. А разнося состоянияпотихоньку, ниже шанс ошибки (наверное).Осталось всего ничего: построить автомат, взяв в качестве состояний группы, и удалив бесполодные и недостижимые состояния (те, из которых нет пути в какое-нибудьитоговое состояние и те, в которые нет входящих стрелок), это вполне успешно делается методом пристального взгляда. Бесплодным состоянием как минимум являетсясостояния, содержащее наше новое состояние17.4.2Почему это работаетНа мой взгляд сам алгоритм говорит сам за себя, но чуть громче он будет говоритьна фоне вот такого автомата:18Глава 5Отрицание, пересечение иобъединение автоматовОтрицание автомата бую цепочку, которую не обрабатываетПересечение автоматов , который успешно обрабатывает лю .- такой автомат 1и 2 3, который успешнообрабатывает и 1, и 2.- такой автоматрабатывает любую цепочку, которую успешнооб- 1 и 2 - такой автомат 3, который успешно обцепочку, которую успешно обрабатывает хотя бы один из 1,Объединение автоматоврабатывает любую 2.Любопытный читатель может спросить: а на кой это вообще все надо?Ну во-первых, такое задание могут дать на экзамене.А во-вторых, такое задание могут дать на экзамене в скрытой форме: вас могут попросить построить автомат, который принимает слова данной грамматики, но толькочетной длины.Тогда можно построить 2 автомата: первый принимает слова данной грамматики, авторой - слова четной длины.

После этого их можно пересечь и радоваться жизни.5.1АлгоритмВсе алгоритмы требуют, чтобы автоматы были полные. Поэтому если надо, дополняем их.195.2ОтрицаниеТут все предельно просто - взяли полный автомат, в нем все состояния, которые небыли конечными, сделали конечными. А все состояния, которые были конечными,сделали неконечными....Ну вот в принципе и все.Вот живой пример:Взяли автоматДополнили и проотрицали5.3Почему это работаетОчевидно, что если цепочка принадлежит исходному языку, то автомат остановитсяв своем конечном состоянии.

А если цепочка не принадлежит - в любом другом состоянии. Поэтому мы просто берем и меняем местами конечные и неконечные состояния.При этом полнота автомата необходима - ведь иначе мы потеряем часть слов, которыеизначально не принадлежали старому языку, но принадлежат новому.205.4Пересечение и объединениеЗдесь мы возьмем 2 следующих автомата (кстати, второй автомат принимает любыеслова четной длины, он реально может пригодиться на экзамене):Возьмем их дополненные версии (да, второй автомат уже полный, можно тихо радоваться):Теперь все будет немножко сложнее. Для начала нужно построить прямое произведение двух автоматов.Можно было бы привести "очень математическое"определение прямого произведения, но оно хоть и очень точное, но вообще не выразительное, поэтому будем объяснять на словах.Прямое произведение автоматов очень понятно смотрится на фоне перемещения вдвухмерном пространстве (ну или в n-мерном, если мы пересекаем n автоматов, нотут я могу понадеяться, что моему бедному читателю никогда не придется делатьпроизведение больше 2х автоматов).Очень удобно представлять, что первый автомат символизирует собой перемещениепо оси , .точку ,а второй - поНачальное состояние - точка(, 1).

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

Если в первомавтомате мы по символу переходим в состояние , а во втором - в состояние , томы просто вспоминаем, что автомат на самом деле один, а мы просто из по переходим в .мы находимся в состоянииДавайте же построим произведение наших полных автоматов:Это куда удобнее делать с помощью таблицы. Для начала нужно сделать таблицудля исходных автоматов: * *122121А теперь строим таблицу произведения (это очень скучно):11112222222211112222111122Это ВСЕ возможные сочетания состояний из первого и второго автомата. Но педантичный читатель мог заметить, что по факту нужны далеко не все (в силу того, чтонекоторые из них недостижимы). Действительно, учитывая, что начальное состояниесостоит из начальных состояний двух старых автоматов (в данном случае получается1),достижимы только состояния1, 1, 1, 2, 2, 2.Поэтому вполне хватит такой таблицы:111222222111222111Остается вопрос: что же взять в качестве множества конечных состояний?Вот тут уже зависит от задачи: если у нас пересечение, то мы берем состояние, состоящее только из конечных состояний старых автоматов (в данном случае2, выделеноочень жирно).Если же у нас объединение, то мы берем состояния, в составе которых есть хотябы одно конечное состояние (в данном случае это1, 2, 2, 2,выделены простойштриховкой).5.5Почему это работаетСаму концепцию произведения я вроде расписал через двухмерное пространство.