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

Московский государственный университет имени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиФормальные языки и автоматыМетодичка для сдающих и пересдающихМожет, зайдет кому-нибудьyung_vimВерсия от сентября 2017 года.Исходник (.tex) и будущие версии:https://github.com/okoshovetc/metodichkaFYAОглавление1234567НКА по РВ41.1Алгоритм. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2Почему это работает. . . . . . . . . . . . . . . . . . . . . . . . . . . . .ДКА по НКА4562.1Алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2Почему это работает. . . .

. . . . . . . . . . . . . . . . . . . . . . . . .ДКА по РВ69103.1Алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2Почему это работает. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1014Минимизация ДКА154.1Алгоритм154.2Почему это работает. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .18Отрицание, пересечение и объединение автоматов195.1Алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195.2Отрицание . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .205.3Почему это работает205.4Пересечение и объединение5.5Почему это работает. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .21. . .

. . . . . . . . . . . . . . . . . . . . . . . . . .23Построение автомата по праволинейной грамматике246.1Алгоритм246.2Почему это работает. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .25Приведение КС-грамматики267.1Алгоритм удаления бесплодных символов . . . . . . . . .

. . . . . . . .267.2Почему это работает277.3Алгоритм удаления недостижимых символов7.4Почему это работает7.5Алгоритм удаления. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .27. . . . . . . . . . . . . . . . . . . . . . . . . . . . .28-правил. . . . . . . . . . . . .

. . . . . . . . . . .1287.6Почему это работает7.7Алгоритм удаления левой рекурсии (примитивной)7.8Почему это работает7.9Алгоритм удаления левой факторизации7.10 Почему это работает89. . . . . . . . . . . . . . . . . . . . . . . . . . . . .28. . . . . . . . . . .29. . . . . . . . . . . . . . . . . . . .

. . . . . . . . .29. . . . . . . . . . . . . . . . .30. . . . . . . . . . . . . . . . . . . . . . . . . . . . .30Построение LL(1)-анализатора318.1Алгоритм318.2Почему это работает8.3Алгоритм разбора цепочки с помощью LL(1)-анализатора. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .

. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .3334Построение LR(1)-анализатора по КС-грамматике359.1Алгоритм359.2Почему это работает9.3Ловля ошибок в зародыше. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .

. .10 Лемма о накачке10.1 Почему это работает394041. . . . . . . . . . . . . . . . . . . . . . . . . . . . .4211 Немножко полезных советов от человека, который не сдал4312 Благодарности442ПредисловиеОднажды я сдавал формалки. Не самый приятный опыт в моей жизни.

Когда я ждалрезультатов, я сказал, что если не сдам, напишу методичку по этому чудесному предмету.Как несложно догадаться, я тогда не сдал.По формалкам уже есть отличное руководство в виде решений задач от Тани (незнаю, кто это, но если бы ее не было, статистика сдаваемости была бы гораздо хуже,я уверен, Таня, спасибо, что ты есть), и казалось бы - зачем я это делаю?Ну во-первых, я сказал, что напишу.Во-вторых, это довольно знатный способ подготовки к пересдаче, который потенциально поможет каким-нибудь людям после меня.В-третьих, наверное, есть смысл восполнить пробел в нормальном "печатном"пособиипо формальным языкам. Ахо Ульмана я не читал (а он, может быть, и норм), но "Теорию Построения Комплияторов" читать совершенно невозможно.В этой методичке я в меру своих возможностей постараюсь не только подробно расписать решения различных задач (это уже есть у Тани), но и более-менее человеческимязыком расписать, как применяемые алгоритмы работают (потому что выучить алгоритм, если есть примерное понимание работы, гораздо проще)За кривой русский язык извиняйте - я ЕГЭ сдал на 30 баллов.3Глава 1НКА по РВ1.1АлгоритмПостроение НКА по РВ делается по определенным правиламКаждое РВ можно разбить на подвыражения, а для простейших подвыражений автомат строится довольно простоНа рисунке далее1.

Е-переход2. Переход по символу3. Переход по4. Переход по5. Переход по| ( или ) (сначала , потом )* (сколько угодно символов ,в т.ч. 0)Справа от простейших НКА нарисованы общие НКА, когда переход совершается понекоторому РВ, где- РВ, а ()- НКА, построенный по нему.4На рисунке изображено построение НКА для РВ1.2(|) * |Почему это работаетПравильность таких построений довольно очевидна, но если не верится, можно походить по полученным НКА по дугам и убедиться, что ничего кроме того, что описанов РВ, по ним составить нельзя.5Глава 2ДКА по НКАГлядя на НКА, полученные по РВ может показаться, что там слишком много лишнихe-переходов, и они бесят.

Также НКА это вам не ДКА: есть неопределенности которыебесят (хотя процесс детерминирования бесит больше). В любом случае существуеталгоритм, позволяющий из большого, но красивого НКА получить маленький и оченьнекрасивый ДКА.2.1АлгоритмВведем некоторые обозначения:1.-()(эпсилон-замыкание состояния R) - множество состояний, в которыеможно попасть из состоянияпо символу.Стоит отметить, что "скачков"можетбыть больше одного, то есть, если в состояниеможно поможно попасть изпо,а из попасть в , то ∈ -(). На языке умных людей это называетсятранзитивностью, но я тут не сложными словами щеголять пришел.2.(, )(достижимые изпопасть из состоянияпопо символу.)- множество состояний, в которые можно(тут скачок должен быть только один)В качестве примера рассмотрим уродца из предыдущей главы:(|) * |61.

Для начала все состояния надо пронумероватьДалее мы начинаем описывать новый автомат с новыми состояниями - тут уже традиционно используют заглавные латинские буквы. Каждое новое состояние описывается множеством старых состояний из первого автомата.2. В качестве начального состояния нового ДКА берутслучае это = -(1),в нашем = {1, 2, 11}.3. Далее формируются следующие правила переходов:(, ) = (, ) + -((, ))(, ) = (, ) + -((, ))И т.д., из которого по символу мы переходимв состояние, описываемое множеством {1, 2, 3, 4, 6, 8, 12, 23}. При этом, если у такогомножества уже есть имя, например , то это попросту значит, что (, ) = . ЕсПусть вышло так, что есть состояниели такого множества раньше не встречалось, то оно добавляется в таблицу состоянийнового ДКА.Звучит сложно и скучно, поэтому лучше посмотреть на живой пример.

= {1, 2, 11};(, ) = (1, ) + (2, ) + (11, );(, ) = {} + {} + {12} = {12};-((, )) = {};(, ) = (, ) + -((, )) = {12} + {} = {12};Состояния {12} у нас еще не было, поэтому добавим его в таблицу состояний и назовем его .Проделаем аналогичные выкладки для символа .(, ) = (1, ) + (2, ) + (11, );(, ) = {} + {3} + {} = {3};-((, )) = {4, 5, 7, 8, 15};(, ) = (, ) + -((, )) = {3} + {4, 5, 7, 8, 15} = {3, 4, 5, 7, 8, 15};Состояния {3, 4, 5, 7, 8, 15} у нас тоже еще не было, поэтому запишем его в таблицусостояний ДКА.Подобные вычисления надо проводить для каждого символа в алфавите, для каждого7нового состояния в таблице до тех пор, пока все старые состояния не будут описаны.С виду может показать, что это очень много писанины, но на деле все эти преобразования делаются в уме и единственное, что нужно реально выписывать, это таблицусостояний.Привожу финальную таблицу переходов для НКА из предыдущей главы.

x x{1, 2, 11}{12}*{3, 4, 5, 7, 8, 15}{13}*{14, 15}xx* {4, 5, 6, 7, 8, 15} {9} x*{4, 5, 7, 8, 10, 15} Удивленный читатель заметит, что некоторые состояния отмечены звездочками испросит, что это. Отвечаю: звездочками помечены конечные состояния. И это следующее правило алгоритма построения:4. Конечными состояниями нового ДКА помечаются такие состояния, которые содержат в себе конечное состояние старого НКА.В данном случае старым конечным состоянием является 15, поэтому все состояния,имеющие в себе 15 становятся конечными.На рисунке изображен полученный ДКА.82.2Почему это работаетРабота алгоритма строится на двух мыслях:1.

Если из одного состояния поможно перейти в несколько других, то зачем намэти другие состояния, если по сути состояние одно, просто разибитое на несколькочастей? (незачем)Грубо говоря, мы стягиваем за-дугимного состояний в одно, как за веревки.2. Если после стягиваний состояний, две дуги, раньше шедшие в два разных состояния, теперь идут в одно стянутое, то действительно ли между этими дугами естьразница? (нет)9Глава 3ДКА по РВДопустим, что у нас есть РВ, которое необходимо преобразовать в ДКА.

И казалосьбы, уже есть целых 2 алгоритма, с помощью которых это можно сделать: сначаластроим НКА, потом по нему же ДКА. Но есть более быстрый алгоритм прямогоперевода.3.1АлгоритмДля начала возьмем все то же РВ из первой главы(|) * |1. Строим расширение РВ: просто дописываем в конце символ конца, как бы странноэто не звучало. Получаем((|) * |)#2. Нумеруем все буквы в нашем РВ (в том числе и символ конца)((|) * |)#1 2 34567 8103. Строим дерево РВ (обязательно помним про приоритеты операций)Также на рисунке по бокам от каждого символа стоит его номер в РВ, чуть позжебудет понятно, зачем.4. Теперь пошла жара: надо определить кучу разных множеств для поддеревьев:()- обнуляемость: может ли поддеревопородить пустую цепочкуТут несколько вариантов: - лист дерева: () = = *, где - некоторое поддерево: () = = | : () = () () = ∙ : () = () () () - первый символ: множество символов, которые могут идти первыми вцепочке, порожденной поддеревом - лист дерева: () = {} = *: () = () = | : () = () ∪ () = ∙ : если (), то () = () ∪ (),иначе () = ()() - последний символ: множество символов, на которые может заканчиваться цепочка, порожденная поддеревом - лист дерева: () = {} = *: () = ()11 = | : () = () ∪ () = : если (), то () = () ∪ (),() = ()иначеНа самом деле все это страшно скучная херня и по большей части решается с помощью метода пристального взгляда и более-менее здравого смысла.Теперь можно пояснить и за странные пометки в предыдущем рисунке: слева стояли (),а справа -()Cейчас прошлый рисунок будет дополнен аналогичными множествами, но уже нетолько для листьев.5.