Ответы 2010 вариант 3 (1119776)
Текст из файла
Вариант 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?
Ответ:
| Класс П | 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. Описать основные особенности программ, программных продуктов и интегрированных программных продуктов.
Ответ: Программа создаётся для решения отдельной задачи автором программы и используется в некоторой конкретной операционной среде. Для программы точно определены и зафиксированы решаемая задача, её автор и операционная среда, для которой предназначена программа. Программа неотделима от автора.
Программным продуктом называется программа, работающая без авторского надзора в рамках некоторого набора операционных сред. Программный продукт может исполняться, тестироваться и модифицироваться без участия автора (он отчуждён от автора). Для программного продукта должна быть разработана достаточно полная пользовательская и техническая документация. Программный продукт должен быть настраиваемым.
Системный (интегрированный) программный продукт есть комплекс (взаимосогласованных) программных продуктов (пакет).
КРИТЕРИИ: За отсутствие комментариев к какому-либо виду программ: -4.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
