A1_2010 (1119652), страница 2

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

Текст из файла (страница 2)

G: S  ACb | Aa

A  Aa | Ca | a

B  Aa | CDb | Bb

C  Ab | b

D  Aa | Cb | a

Ответ: Контекстно-свободная грамматика называется приведённой, если в ней нет бесполезных (бесплодных и недостижимых) символов.

1. Удаление бесплодных символов. Строится множество N, из элементов которого за некоторое число шагов выводятся терминальные символы:

1. N₀ = 

2. N₁ = {A, C, D}, N₁  N₀

3. N₂ = { A, B, C, D, S}, N₂  N₁

4. N₃ = { A, B, C, D, S}, N₃ = N₂

Бесплодных символов в грамматике G не обнаружено.

2. Удаление недостижимых символов. Строится множество V, в которое помещаются символы, за некоторое число шагов выводимые из символа S:

1. V₀ = {S}

2. V₁ = {S, A, C}, V₁  V₀

3. V₂ = {S, A, С}, V₂ = V₁

Символы B и D из алфавита грамматики G являются недостижимыми, их и правила их содержащие можно удалить из грамматики:

G_прив: S  ACb | Aa A  Aa | Ca | a C  Ab | b

КРИТЕРИИ: Нет определения или оно неверно: -5.

За ошибку при преобразовании: -7.

10. По приведенной обратной польской записи фрагмента программы, написанной на языке Си++, восстановите этот фрагмент двумя способами: сначала, пользуясь операторами условного и безусловного перехода на метку, а затем (если это возможно), пользуясь только операторами структурного программирования без переходов. Операция ПОЛИЗ '@' соответствует унарной операции изменения знака.

Ответ:

M: if (! (x ++ + 4 <= (y – 5) * 20)) goto L;

a = (x – 8) * 7 – y / (– x + 2);

goto M;

L: b = (x = ++ y);

while (x ++ + 4 <= (y – 5) * 20) a = (x – 8) * 7 – y / (– x + 2); b = (x = ++ y);

КРИТЕРИИ: за неверный ответ на первый вопрос: -7.

за неверный ответ на второй вопрос, если первый вариант верен: -3, иначе: -10

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

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