Ответы_экзамен_2009 (1115077)
Текст из файла
Вариант 1 ОТВЕТЫ и критерии оценки
За каждую задачу — максимум 10 баллов.
| 1. Дана грамматика G:
S Aa | cSad | ε cAad cBad B c cB cBc | найти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1. Ответ: k 0 (есть S ε и S встречается в правой части правила S cSad ) | (б) Каким из перечисленных классов принадлежит язык L(G) ? Ответ:
|
(в) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы).
| Ответ: L(G) {сn (ad)n | n0} КРИТЕРИИ: (а) нет ответа; неверный ответ : –3 (обоснование не обязательно) (б) за каждый неверный или отсутствующий ответ: –1 (т.е. всего до –4 за этот пункт) (обоснование не обязательно) (в) описание отсутствует или с ошибками: –3 | ||
| 2. (а) Дать определение недостижимого символа. (б) Эквивалентны ли данные КС-грамматики G1 и G2 ? Ответ обосновать. G1 : S BAa A Aa | a | B b | G2 : S E | BAa D dDd | c E EaD | Ed A Aa | ADE | a | B DbE | b | |
Ответ:
(а) символ x T N называется недостижимым в грамматике G T, N, P, S , если он не появляется ни в одной сентенциальной форме этой грамматики.
(б) Да, эквивалентны. Грамматика G1 является результатом применения к грамматике G2 алгоритма приведения КС-грамматики. Другое обоснование: L {ba n | n1} L(G1) L(G2) .
КРИТЕРИИ: (а) нет ответа; определение с ошибками: –5
(б) нет ответа; неверный ответ; нет обоснования; неверное обоснование: –5
| 3 | ( (б) Детерминирован ли разбор по данной диаграмме ? Объясните ответ. | |
| (в) Если разбор по диаграмме состояний A недетерминированный (т.е. конечный автомат A — недетерминированный), то с помощью соответствующего алгоритма построить эквивалентный детерминированный автомат AD , иначе — написать для A программу-анализатор на языке C++. | ||
. По леволинейной грамматике G была построена диаграмма состояний A:
a) Восстановить по диаграмме A грамматику G:Ответ: (a) G: S | B
B Bb| Aa
A Aa | Bb | a
(б) Разбор недетерминирован, т.к. автомат A не является детерминированным: из состояния A возможен переход в более чем одно состояние (по символу а). [или: из состояния B возможен переход в более чем одно состояние (по символу b)]
(в)
Построим таблицу переходов для AD :
a b { H } { A } { S } { A } { A, B } { A, B } { A, B } { A, B } { S } { S }
Начальное состояние: { H }. Заключительное состояние: { S }.
AD :
Допускаются другие способы построения, дающие в итоге такой же автомат AD с точностью до обозначений вершин.
КРИТЕРИИ: (а) нет ответа; грамматика построена, но неэквивалентная или не соответствующая
диаграмме : –3
(б) нет ответа; неверный ответ; ошибочное объяснение : –3
(в) нет ответа или программа на C++ приведена;
неэквивалентный или недетерм. автомат построен : –4
| 4. | Имеется клетчатый лист бумаги, бесконечный вправо и вниз. В левом верхнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {a, b}: a — переместить перо на одну клетку вправо; | |
| b — переместить перо по диагонали на одну клетку влево-вниз. Например, по последовательности aaaaabbbbbaaaaa интерпретатор построит букву «Z» размера 55, изображенную на рисунке. Построить грамматику с терминальным алфавитом {a, b}, описывающую буквы «Z» любого размера nn, n 1. В грамматике должно быть не более 7 правил вывода (считая альтернативы). |
| |
Ответ: Описание буквы «Z» размера nn — это цепочка anbnan. Следовательно, требуется построить грамматику, порождающую язык { anbnan | n 1}: S ABSa | Aba
BA AB
Bb bb
Ab ab
Aa aa
КРИТЕРИИ: порождается пустая цепочка: –5
имеется лишняя (непустая) или недостающая цепочка: –10
за каждое лишнее правило: –3 (количество правил в условии дано с запасом)
Замечание. Грамматика S ABSa | ABa
BA AB
B b
A a ошибочная, так как порождает лишние цепочки, напр.: ababaa.
| 5. | (а) (б) | Сформулируйте достаточное условие применимости метода рекурсивного спуска с учетом возможной -альтернативы (т.н. «канонический вид» КС-грамматики). Выполняется ли это условие для грамматики G ? Обоснуйте ответ. G: S aAS | bB | A aAca | bBb B cB | |
Ответ: (а) Достаточное условие: каждая группа правил с одинаковой левой частью имеет один из перечисленных ниже видов и выполняются дополнительные условия:
-
либо X → ,
где (T N)* и это единственное правило вывода для этого нетерминала; -
либо X → a11 | a22 | ... | ann,
где ai T для всех i 1, 2,..., n ; ai aj для i j; i (T N )*, т. е. если для нетерминала X правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть попарно различными;
-
либо X → a11 | a22 | ... | ann | ,
где ai T для всех i 1, 2,..., n; ai aj для i j; i (T N )*, и first (X ) follow (X ) .
Замечание. Допускаются обозначения VT , VN для обозначения алфавитов терминальных и нетерминальных символов, и обозначение V для их объединения. V T N (V VT VN)
(б) Да, т.к. все непустые альтернативы начинаются с попарно различных терминалов, first (S ) follow (S ) , и first (B ) follow (B ) .
[ first (S ) {a, b}, follow (S ) ; first (B ) {c}, follow (B ) {b} ]
КРИТЕРИИ: (а) нет ответа, ошибки в формулировке: –5
(б) нет ответа; неверный ответ; нет обоснования; ошибочное обоснование: –5
| 6. | Описать грамматику, порождающую язык Lвх { d na m a n | m,n 0 }, и вставить в нее действия вида cout << ′символ′ ; так, чтобы для любых целых m, n 0 в процессе анализа рекурсивным спуском входной цепочки d na ma n печаталась бы цепочка cbna m. |
Ответ. Соглашение : запись a является сокращением cout << ′a ′;
Lвх { d na m+ n| m,n 0 } { d n a n a m| m,n 0 } (входной язык). Грамматика для Lвх , к которой применим метода рек. спуска выглядит так:
S AB
A dAa |
B aB |
Lц { cbna m | m,n 0 } (целевой язык).
Грамматика с действиями:
| S AB A dAa b | с B a a B | | или : S сAB A d b Aa | B a a B | |
КРИТЕРИИ:
Грамматика не порождает Lвх , или не генерирует Lц : 0
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
