2012 Примерное решение экзаменационных задач (1134910)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

конспекты занятий по курсу«Теория и реализация языков программирования»ПриложениеПримерное решение экзаменационных задач от 9.11.12 (готовимся кпересдаче)Задача 1.Задача 3.Задача 4.Тоже в pdfЗадача 1.Заданы языки L1 = {a n b 2 n | n ≥ 0} и L2 = {b 2 n a n | n ≥ 0} . Для языка1. Построить МП-автомат;2. Построить однозначную КСГ.Намётки к решению.С учётом того, что имеется простой и быстрый алгоритм переход от КСГ к МПА(GN-теорема), а обратный переход в общем случае заметно сложнее и болеетрудоёмок, построим сначала однозначную КСГ.Для этого:2.1. Определим общие цепочки языков L1 и L2 :L1 ∩ L2 = ε2.2.

Построим отдельные КСГ для L1 и L2 , не порождающие общую цепочку (ε):L1 :S1 → aS1bb | abbL2 :S 2 → bbS 2 a | bba2.3. Строим КСГ для итерации ( L1 ∪ L2 ) * :S → ε | S0S 0 → S1S 0 | S 2 S 0 | S1 | S 22.4. Обосновываем однозначность полученной КСГ (например, построениемдерева вывода).1.

По GN-теореме переходим от грамматики к МПА. Итого, у нас должнополучиться 12 функций перехода МПА (10 по числу правил КСГ и 2 по числуосновных знаков алфавита).Задача 3.Язык L задан выражением (ab)*(a|b)(ba)*.Построить минимальный ДКА, допускающий языкL (дополнение).Эквивалентен ли этот ДКА автомату, допускающему язык, заданный грамматикойG=({A,B,C,D,E},{a,b},{A→ε, A→aB, A→bC, B→bD, B→b,C→bE, C→b, D→aB, D→bC, E→aC}, A).Намётки к решению.Эта задача на знание и умение применять следующие алгоритмы:А. Построение ДКА по РВ (прямое или через НКА)Б.

Построение полного ДКАВ. Построение ДКА для дополнения языка L по ДКА, соответствующему L.Г. Минимизации полного ДКА.Д. Проверки эквивалентности двух ДКАА. Прямое построение ДКА по РВ быстрее, чем РВ –>НКА –>ДКА, и, в отличиеот последнего, часто сразу приводит к минимальному ДКА (см. пример). Поэтомувоспользуемся этим алгоритмом.(a b)* (a | b)( b a )* #1 2i1345 67firstpos (root) = {1, 3, 4}followpos (i)2A = 1, 3, 4a a babBC21, 3, 4B* = 2, 5, 7–DC* = 5, 7–ED = 1, 3, 4, 6BCE =6C–b b #35, 7b #45, 7a a b a56a65, 72, 3Диаграмма ДКА:2, 3a1, 4, 5AabDB1, 4, 5bbECbaПоскольку полученный ДКА не является полным (к примеру, из вершин В и Cнет переходов по а, а из вершины Е – по b), а алгоритм получения дополнения дляДКА требует на входе полный ДКА, то пополним автомат, добавив недопускающеесостояние F и переходы в него из неполных в указанном выше смысле вершин(включая и само F):Полный ДКА:aa, bAaaFDBbbbabECbaДополнение, как известно, может быть получено из полного ДКА заменой егодопускающих состояний на недопускающие, а недопускающих на допускающие:Дополнение ДКА:aAaaDBbba, bFbabCEbaОстаётся минимизировать полученный ДКА и сравнить задаваемый им язык сязыком грамматики G.

Пример минимизации можно посмотреть здесь.По данной в условии грамматике G непосредственно строится ДКА:aАabBDbbCEbaИз диаграммы видно, что автоматы различаются на одно допускающеесостояние, что позволяет легко построить контрпример цепочки, которая явно непринимается ДКА по G,например, аaa или bbb, но столь же явно входит в дополнение L.Ответ: дополнение заданного РВ языка и грамматика G задают разные языки(не эквивалентны).Задача 4.L1 = (a | b)* aab(a | b)* .

Язык L = {w | w ∈ L1 , | w |a ≥| w |b } .1. Является ли дополнение языка L КС-языком?2. Является ли дополнение L регулярным языком?Наброски решенияДанная задача на знание свойств регулярных языков, а также свойствобъединения регулярного языка и КС-языка.1.

Заметим, что определение языка L в условии нашей задачи естественнопереписывается как пересечение двух языков – дополнения L1 и L2 :L1 = (a | b)* aab(a | b)*L2 = {w ∈ ( a , b)* : | w |a ≥| w |b }То есть L = L1 ∩ L2 .2. Тогда дополнение языка L естьL = L1 ∩ L2 = L1 ∪ L2 (по правилу Моргана)3. Вид дополнения для L2 понятен:L2 = {w ∈ ( a , b)* : | w |a <| w |b }Этот и подобные языки хорошо нам знакомы по заданию.

Он является КСязыком, подтверждением чему может служить, например, КСГ, который легконапишет каждый, кто сделал задание по ТРЯП.<КСГ для языка L2 >4. В тоже время данный язык не является регулярным, что доказываетсяприменением леммы о разростании для регулярных языков:< доказательство нерегулярности языка L2 >5. Поскольку из лекционного курса известно, что пересечение КС-языка ирегулярного языка есть КС-язык, то дополнение языка L является КС-языком..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)