2009 вариант 1, 2, 3 ответы (1119755)
Текст из файла
Вариант 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
Порождает Lвх и формально генерирует соответствующие цепочки из Lц ,
но метод рек. спуска неприменим: -5
7. Дайте определение системы программирования. Перечислите основные компоненты классической системы программирования на базе ОС UNIX (ЯП Си). Кратко опишите назначение каждого из основных компонент.
Ответ:
Система программирования — это комплекс программных инструментов и библиотек, который поддерживает весь технологический цикл создания программного продукта (ПП).
[Как вариант: Система программирования — это комплекс программных средств (инструментов, библиотек), предназначенных для поддержки программного продукта на протяжении всего жизненного цикла этого программного продукта.]
Основные компоненты системы программирования: 1. Транслятор (проверяет синтаксическую правильность программ и переводит их с языка программирования на машинный язык, что и позволяет выполнить их на ЭВМ). 2. Макрогенератор или макропроцессор (работает непосредственно перед транслятором, используется для получения макрорасширения исходной программы). 3. Редактор связей или компоновщик (предназначен для связывания между собой (по внешним данным) объектных файлов, порождаемых компилятором, а также файлов библиотек, входящих в состав СП). 4. Редактор текстов (используется для составления и редактирования программ на языке программирования).
5. Отладчик (используется для проверочных запусков программ, локализации и исправления ошибок). 6. Библиотеки (облегчают работу программиста, предоставляя готовые фрагменты решения тех или иных подзадач программы, используются на этапе трансляции и исполнения).
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
