A3_2010 (1119654)
Текст из файла
Вариант 3_2010 Ф.И.О.___________________________________№ группы________
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
За каждую задачу — максимум 10 баллов
1 S aA | A A Bb | B | Ac B c | Bc | ( Ответ: L(G) { aicnbjcm | i, j {0,1}, n 1, m 0} | (б) Каким из перечисленных классов принадлежит язык L(G)? Ответ:
|
(в) Каким из перечисленных классов грамматик принадлежит G?
Ответ:
Класс П | G П? (да/нет) |
контекстно-свободные | да (-1) |
контекстно-зависимые | да (-1) |
регулярные | нет (-3) |
грамматики типа 0 | да (-1) |
неукорачивающие | да (-1) |
КРИТЕРИИ: (а) описание отсутствует или с ошибками: –4
(б), (в) снимаемые баллы за каждый неверный или отсутствующий ответ в таблице, обоснование не обязательно
2. Описать иерархию классов языков по Хомскому. Привести примеры трех языков, относящихся к различным уровням иерархии.
Ответ: (а) Тип 3 (регулярные) Тип 2 (КС) Тип 1 (КЗ) Тип 0
(б) При обосновании класса языка можно опираться на утверждения
-
языки вида L={an|n1} – типа 3, регулярные.
-
языки вида L={anbn|n1} – типа 2, контекстно-свободные.
-
языки вида L={anbncn|n1} – типа 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
4. | Имеется клетчатый лист бумаги, бесконечный вправо и вверх. В левом нижнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {с, a, e}: c — переместить перо на одну клетку вверх; | |
a — переместить перо на одну клетку вправо; e — переместить перо на одну клетку вниз. Например, по последовательности ccccaa интерпретатор построит букву «Г» размера 42, изображенную на рисунке. Построить грамматику с терминальным алфавитом {c, a}, описывающую буквы «Г» любого размера nm, n,m 1. В грамматике должно быть не более 4 правил вывода (считая альтернативы). |
| |
В построенную грамматику добавить действия вида cout << ′символ′; так, чтобы описание буквы «Г» размера nm переводилось в описание буквы «П» размера (n+1) m. |
Ответ: Описание буквы «Г» размера nm — это цепочка cnam. Следовательно, требуется построить грамматику, порождающую язык {cnam | n,m 1}: S сS | cA
A aA | a
Соглашение: запись a является сокращением cout << “a”;
Грамматика с действиями: S ссSe | cccAee
A aaA | aa
КРИТЕРИИ: порождается пустая цепочка: –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 α | β выполняются следующие условия:
-
first(α) Ç first(β) = ;
-
справедливо не более чем одно из двух соотношений: α ε, β Þ ε;
-
если β Þ ε, то 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, так как принтер может начудить со шрифтами.