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

конспекты занятий по курсу«Теория и реализация языков программирования»ПриложениеПримерное решение экзаменационных задач от 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 является КС-языком..