Формальные языки и автоматы - Методичка для сдающих и пересдающих (1134640)
Текст из файла
Московский государственный университет имени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиФормальные языки и автоматыМетодичка для сдающих и пересдающихМожет, зайдет кому-нибудь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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
