конспекты занятий по курсу

 «Теория и реализация языков программирования»

Приложение

^

=

_

Примерное решение экзаменационных задач от 9.11.12 (готовимся к пересдаче)

                                   Задача 1.

                                                           Задача 3.

                                                                                   Задача 4.

                                                           Тоже в pdf     

Задача 1.

Заданы языки  и . Для языка

1.     Построить МП-автомат;

2.     Построить однозначную КСГ.

Намётки к решению.

С учётом того, что имеется простой и быстрый алгоритм переход от КСГ к МПА (GN-теорема), а обратный переход в общем случае заметно сложнее и более трудоёмок, построим сначала однозначную КСГ.

Для этого:

2.1. Определим общие цепочки языков L₁ и L₂ :

2.2.  Построим отдельные КСГ для L₁ и L₂ , не порождающие общую цепочку (e):

2.3.  Строим КСГ для итерации  :

2.4.  Обосновываем однозначность полученной КСГ (например, построением дерева вывода).

1. По GN-теореме переходим от грамматики к МПА. Итого, у нас должно получиться 12 функций перехода МПА (10 по числу правил КСГ и 2 по числу основных знаков алфавита).

Задача 3.

Язык L задан выражением (ab)*(a|b)(ba)*.

Построить минимальный ДКА, допускающий язык (дополнение).

Эквивалентен ли этот ДКА автомату, допускающему язык, заданный грамматикой 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.

Г. Минимизации полного ДКА.

Д. Проверки эквивалентности двух ДКА

А. Прямое построение ДКА по РВ быстрее, чем РВ –>НКА –>ДКА, и, в отличие от последнего, часто сразу приводит к минимальному ДКА (см. пример). Поэтому воспользуемся этим алгоритмом.

                        firstpos (root) = {1, 3, 4}

i

followpos (i)

a

b

1

2

B

C

2

1, 3, 4

–

D

3

5, 7

–

E

4

5, 7

B

C

5

6

C

–

6

5, 7

Диаграмма ДКА:

2, 3

2, 3

1, 4, 5

1, 4, 5

Поскольку полученный ДКА не является полным (к примеру, из вершин В и C нет переходов по а, а из вершины Е – по b), а алгоритм получения дополнения для ДКА требует на входе полный ДКА, то пополним автомат, добавив недопускающее состояние F и переходы в него из неполных в указанном выше смысле вершин (включая и само F):

Полный ДКА:

Дополнение, как известно, может быть получено из полного ДКА заменой его допускающих состояний на недопускающие, а недопускающих на допускающие:

Дополнение ДКА:

Остаётся минимизировать полученный ДКА и сравнить задаваемый им язык с языком грамматики G. Пример минимизации можно посмотреть здесь.

По данной в условии грамматике G непосредственно строится ДКА:

Из диаграммы видно, что автоматы различаются на одно допускающее состояние, что позволяет легко построить контрпример цепочки, которая явно не принимается ДКА по G,

например, аaa или bbb, но столь же явно входит в дополнение L.

Ответ: дополнение заданного РВ языка и грамматика G задают разные языки (не эквивалентны).

Задача 4.

 . Язык .

1. Является ли дополнение языка L КС-языком?

2. Является ли дополнение L регулярным языком?

Наброски решения

Данная задача на знание свойств регулярных языков, а также свойств объединения регулярного языка и КС-языка.

1. Заметим, что определение языка L в условии нашей задачи естественно переписывается как пересечение двух языков – дополнения L₁ и L₂ :

То есть .

2. Тогда дополнение языка L есть

 (по правилу Моргана)

3. Вид дополнения для L₂ понятен:

Этот и подобные языки хорошо нам знакомы по заданию. Он является КС-языком, подтверждением чему может служить, например, КСГ, который легко напишет каждый, кто сделал задание по ТРЯП.

<КСГ для языка  >

4. В тоже время данный язык не является регулярным, что доказывается применением леммы о разростании для регулярных языков:

< доказательство нерегулярности языка  >

5. Поскольку из лекционного курса известно, что пересечение КС-языка и регулярного языка есть КС-язык, то дополнение языка L является КС-языком.

^

=

_