A1_2010 (1119652)

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

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

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

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

(в) Классификация: найти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1.

Ответ: k  0 (есть укорачивающее правило A  ε и не КС-правило EE  EEE)

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

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

(обоснование не обязательно)

(в) нет ответа; неверный ответ: –4 (обоснование не обязательно)

2. Дать определение эквивалентных грамматик. Приведите примеры эквивалентных и почти эквивалентных грамматик. Могут ли неэквивалентные грамматики порождать один и тот же язык?

Ответ:

(а) Грамматики G₁ и G₂ называются эквивалентными, если их языки совпадают, L(G₁) = L(G₂). (б) Например, из трёх разных грамматик:

G₁ = ({0,1}, {A,S}, P₁, S) и G₂ = ({0,1}, {S}, {S  0S1 | 01}, S)

P₁: S  0A1 G₃ = ({0,1}, {S}, {S  0S1 | }, S)

0A  00A1

A   G₁ и G₂ эквивалентны, L(G₁) = L(G₂) = {0ⁿ1ⁿ | n > 0}.

G₁ (G₂) и G₃ почти эквивалентны, L(G₃) = {0ⁿ1ⁿ | n  0}

(в) Нет, это невозможно по приведённому определению.

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

(б) за каждый из двух отсутствующих примеров: –3

(в) нет ответа; неверный ответ: –5

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

G: H  bA | bB | aC

A  bC

B  aC

C  aA | bB | 

Ответ: Автомат недетерминирован G’: S  C

A  Ca

B  Cb

C  Ab | Ba | Da | Db | a

D  b

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

КРИТЕРИИ: (а) построен неэквивалентный или недетерминированный автомат: –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Ae

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

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

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

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

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

void S () { if (c == ‘b’) { c = GetS (); A ();

if (c == ‘a’) { c = GetS (); C (); D (); } else Error ();

if (c == ‘’) return;

}

Error ();

}

void A () { if (c == ‘a’) { c = GetS (); A (); } else B (); }

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

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

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

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

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

A  aA | B B  bB | C

C  aC | D D  bD | A

Анализатор некорректен: он, например, зацикливается на цепочке “b”.

Достаточное условие применимости метода рекурсивного спуска для грамматик без эпсилон-правил:

1. либо A  , где   (T  N)^* и это единственное правило вывода для A;

2. либо A  a₁₁ | a₂₂ | ... | a_n_n, где a_i  T для i = 1,2,...,n; a_i  a_j для i  j; _i  (T  N)^*.

Грамматика G достаточным условиям не соответствует: не все правила для нетерминальных символов A, B, C и D начинаются с терминальных символов.

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

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

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

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

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

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

6. Дать определение системы программирования. Перечислить основные компоненты систем программирования и их основное назначение.

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

• средства интеграции компонентов системы программирования (-1)

• редакторы текстов (-2)

• трансляторы: интерпретаторы, компиляторы и ассемблеры, вместе с макрогенераторами (-2)

• библиотеки (-2)

• редакторы связей (-2)

• средства конфигурирования (-1)

• отладчики (-2)

• средства тестирования (-1)

• профилировщики (-1)

• справочные системы (-1)

КРИТЕРИИ: За пропуск компонентов снижать на 1-2 балла.

7. Выпишите не менее 5 различных видов внутреннего представления программ, используемых при компиляции.

Ответ:

• Связные списочные структуры, представляющие синтаксическое дерево

• Многоадресный код с явно именуемыми результатами (тетрады)

• Многоадресный код с неявно именуемыми результатами (триады)

• Инфиксная запись

• Префиксная запись

• Постфиксная запись

• Язык ассемблера

КРИТЕРИИ: За каждый пропущенный из необходимых 5 видов: -2.

8. С какими компонентами интегрированных систем программирования взаимодействуют входящие в них символьные отладчики? Какую помощь и для чего оказывают отладчикам эти компоненты?

Ответ: С текстовыми редакторами, компиляторами и редакторами связей. Текстовые редакторы обеспечивают доступ к текстовой структуре программе (для расстановки точек останова и пошагового исполнения программы). Компиляторы и редакторы связей обеспечивают доступ к информационным таблицам имен, адресов, к описаниям областей памяти (для выдачи информации в терминах входной программы).

КРИТЕРИИ: За пропуск какого-либо компонента: -3 (за каждый пропуск).

За пропуск объяснения какого-либо взаимодействия компонентов: -2 (за каждый).

9. Дать определение приведённых грамматик. Преобразовать контекстно-свободную грамматику G к приведённому виду, выписывая результаты применения каждого шага используемого алгоритма.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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