A3_2010 (Варианты языков от Волковой)

Вариант 3_2010 Ф.И.О.___________________________________№ группы________

За каждую задачу — максимум 10 баллов

(в) Каким из перечисленных классов грамматик принадлежит G?

Ответ:

КРИТЕРИИ: (а) описание отсутствует или с ошибками: –4

(б), (в) снимаемые баллы за каждый неверный или отсутствующий ответ в таблице, обоснование не обязательно

2. Описать иерархию классов языков по Хомскому. Привести примеры трех языков, относящихся к различным уровням иерархии.

Ответ: (а) Тип 3 (регулярные)  Тип 2 (КС)  Тип 1 (КЗ)  Тип 0

(б) При обосновании класса языка можно опираться на утверждения

• языки вида L={aⁿ|n1} – типа 3, регулярные.

• языки вида L={aⁿbⁿ|n1} – типа 2, контекстно-свободные.

• языки вида L={aⁿbⁿcⁿ|n1} – типа 1, контекстно-зависимые.

КРИТЕРИИ: (а) нет ответа или иерархия приведена с ошибками: –5

(б) нет ответа; неверный ответ: –2 (в отношении каждого из трех примеров)

3. Построить по заданной грамматике G конечный автомат (в виде ДС). Если автомат оказался детерминированным, построить анализатор на Си, иначе – преобразовать автомат в соответствии с алгоритмом преобразования НКА в эквивалентный ДКА и по полученному ДКА построить праволинейную грамматику.

G: S  A | B

A  Aa | Ab | Ba | Bb | b

B  Aa | Ab | Ba | Bb | a

Ответ: Автомат недетерминирован

G’: H  aB | bA

A  aC | bС

B  aC | bС

C  aC | bС | 

Функция переходов исходного автомата

b a b a b a a b a b  	δ (H, a) = B δ (H, b) = A	δ (A, a) = A δ (A, a) = B δ (A, b) = A δ (A, b) = B δ (A, ) = S	δ (B, a) = A δ (B, a) = B δ (B, b) = A δ (B, b) = B δ (B, ) = S
	Функция переходов детерминированного автомата (C  AB)
	δ (H, a) = B δ (H, b) = A	δ (A, a) = С δ (A, b) = C δ (B, a) = C δ (B, b) = С	δ (C, a) = С δ (C, b) = С δ (A, ) = S δ (B, ) = S δ (С, ) = S

КРИТЕРИИ: (а) нет или неправильная диаграмма состояний исходного автомата: –5

(б) построен неэквивалентный или недетерминированный автомат: –5

(в) праволинейная грамматика построена, но неэквивалентная или не соответствующая новой диаграмме: –5

(г) нет ответа или приведена программа анализатора: 0

Ответ: Описание буквы «Г» размера nm — это цепочка cⁿa^m. Следовательно, требуется построить грамматику, порождающую язык {cⁿa^m | n,m 1}: S  сS | cA

A  aA | a

Соглашение: запись a является сокращением cout << “a”;

Грамматика с действиями: S  ссSe | cccAee

A  aaA | aa

КРИТЕРИИ: порождается пустая цепочка: –5

имеется лишняя (непустая) или недостающая цепочка: –10

за каждое лишнее правило: –3

5. Восстановить грамматику по заданному анализатору на С++. Сформулировать критерий применимости метода рекурсивного спуска для контекстно-свободных грамматик. Соответствует ли полученная грамматика этому критерию? Обосновать свой ответ. Корректен ли данный анализатор? Обосновать свой ответ (доказать корректность или найти примеры некорректного поведения анализатора).

void S () { if (c != ‘b’) Error ();

c = GetL (); A (); B (); C (); D ();

if (c != ‘b’) Error ();

c = GetL (); A (); D ();

}

void A () { C(); E(); }

void B () { if (c == ‘b’) { c = GetL (); C (); } else D (); }

void C () { if (c == ‘a’) { c = GetL (); D (); } }

void D () { if (c == ‘b’) { c = GetL (); E (); } else A (); }

void E () { if (c == ‘a’) { c = GetL (); B (); } }

Ответ: Восстановленная грамматика имеет вид:

G = ({a, b}, {A, B, C, D, S}, P, S) P: S  bABCDbAD

A  CE

B  bC | D

C  aD | ε

D  bE | A

E  aB | ε

Анализатор некорректен: он выдаёт ошибку на правильной цепочке “bb”.

Критерий применимости метода рекурсивного спуска для грамматик с эпсилон-правилами:

Метод рекурсивного спуска применим, если и только если для любых двух правил X  α | β выполняются следующие условия:

1. first(α) Ç first(β) = ;

2. справедливо не более чем одно из двух соотношений: α  ε, β Þ ε;

3. если β Þ ε, то first(α) Ç follow(X) = .

Грамматика G показанным условиям не соответствует: для двух правил B  bC и B  D имеем: first (bC) Ç first (D) = {b} Ç {ab}¹ .

КРИТЕРИИ: Неправильно восстановлена грамматика: -5.

Неверная формулировка критерия применимости: -5.

Неверный ответ на вопрос о соответствии грамматики критерию применимости: -3.

Нет обоснования соответствия/несоответствия грамматики: -2.

Неверный ответ на вопрос о корректности анализатора: -3.

Нет обоснования корректности (не найден пример “плохой” цепочки): -2.

6. Описать основные особенности программ, программных продуктов и интегрированных программных продуктов.

Ответ: Программа создаётся для решения отдельной задачи автором программы и используется в некоторой конкретной операционной среде. Для программы точно определены и зафиксированы решаемая задача, её автор и операционная среда, для которой предназначена программа. Программа неотделима от автора.

Программным продуктом называется программа, работающая без авторского надзора в рамках некоторого набора операционных сред. Программный продукт может исполняться, тестироваться и модифицироваться без участия автора (он отчуждён от автора). Для программного продукта должна быть разработана достаточно полная пользовательская и техническая документация. Программный продукт должен быть настраиваемым.