V2_2010 (1119656)
Текст из файла
Вариант 2_2010 Ф.И.О.___________________________________№ группы________
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1. Дана грамматика G: S aA | A A BbB | Bb | B B C | CC CC CCC C c |
(a) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы). |
(б) Каким из перечисленных классов грамматик принадлежит G?
|
(в) Тип языка: найти такое целое k, что язык L(G) является языком типа k и не является языком типа k+1.
2. Дать определение порождающей грамматики. Какие ограничения на использование терминальных и нетерминальных символов в правилах грамматики наложены этим определением? Предложите какую-либо грамматику для языка L = {(a,b)+} и укажите на этом примере все компоненты, упоминаемые в определении грамматики.
3. Дана диаграмма состояний конечного автомата. Построить по этой диаграмме соответствующую леволинейную грамматику. Если заданный автомат детерминирован, построить анализатор на Си, иначе – преобразовать автомат в соответствии с алгоритмом преобразования НКА в эквивалентный ДКА, и по полученному ДКА построить праволинейную грамматику.
a
a
a
a
b
b
| 4. | Имеется клетчатый лист бумаги, бесконечный вправо и вверх. В левом нижнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {с, a, e}: c — переместить перо на одну клетку вверх; | |
| a — переместить перо на одну клетку вправо; e — переместить перо на одну клетку вниз. Например, по последовательности cccccaaaa интерпретатор построит букву «Г» размера 54, изображенную на рисунке. Построить грамматику с терминальным алфавитом {c, a}, описывающую буквы «Г» любого размера nm, n,m 1. В грамматике должно быть не более 4 правил вывода (считая альтернативы). |
| |
| В построенную грамматику добавить действия вида cout << ′символ′; так, чтобы описание буквы «Г» размера nm переводилось в описание буквы «П» размера n (m+1). | ||
5. Восстановить грамматику по заданному анализатору на С++. Сформулировать достаточное условие применимости метода рекурсивного спуска для грамматик с эпсилон-правилами. Соответствует ли полученная грамматика данному условию? Обосновать свой ответ. Корректен ли данный анализатор? Обосновать свой ответ (доказать корректность или найти примеры некорректного поведения анализатора).
void S () { if (c == ‘1’) { c = GetL (); A();
if (c != ‘0’) Error ();
c = GetL (); C(); D();
if (c != ‘1’) Error ();
c = GetL ();
}
else Error ();
}
void A () { if (c == ‘0’) { c = GetL (); A(); }
else if (c == ‘1’) { c = GetL (); B(); }
else Error ();
}
void B () { if (c == ‘0’) { c = GetL (); C(); }
else if (c == ‘1’) { c = GetL (); B(); }
else Error ();
}
void C () { if (c == ‘0’) { c = GetL (); C(); }
else if (c == ‘1’) { c = GetL (); D(); }
else Error ();
}
void D () { if (c == ‘1’) { c = GetL (); D(); } }
6. Описать основные задачи ассемблеров, компиляторов и интерпретаторов. В чём сходство и различие этих компонентов систем программирования?
7. Нарисовать схему однопроходного компилятора. Каким образом в таких компиляторах взаимодействуют лексический и синтаксический анализаторы? Какой из анализаторов является ведущим в таком взаимодействии?
8. Описать основные подходы, использующие поведенческие и структурные тесты программ. В чем их основные различия?
9. Дать определения бесплодных и недостижимых символов алфавита контекстно-свободной грамматики. Преобразовать контекстно-свободную грамматику G к приведённому виду, выписывая результаты применения каждого шага используемого алгоритма.
G: S Ab | Ba
A Ca
B Bb | Da
C Aa | Bb | a | b
D Db | Ba
10. По приведенной обратной польской записи фрагмента программы, написанной на языке Си++, восстановите этот фрагмент двумя способами: сначала, пользуясь операторами условного и безусловного перехода на метку, а затем (если это возможно), пользуясь только операторами структурного программирования без переходов. Операция ПОЛИЗ '@' соответствует унарной операции изменения знака.
| ПОЛИЗ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| &a | x | @ | 11 | * | y | x | @ | / | — | += | ; | &x | #+ | 5 | &y | +# |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | |
| — | x | + | 1 | — | <= | 28 | !F | 1 | ! | &y | &x | y | 8 | + | = | 7 | + | = | ; |
|
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
