A3_2010 (1119654)

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

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

Вариант 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С | 

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

КРИТЕРИИ: (а) нет или неправильная диаграмма состояний исходного автомата: –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. Описать основные особенности программ, программных продуктов и интегрированных программных продуктов.

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

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

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

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

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

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

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

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