2012 вариант 2 (1119763)
Текст из файла
Вариант 2_2012 Ф.И.О.___________________________________№ группы________
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1. Дана грамматика G: S aS |aSb|aAb|ab aAb aAbb |ab aaAbb aaAbb aS aaS |
(a) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы). |
(б) Каким из перечисленных классов грамматик принадлежит G? Ответ:
|
(в) Тип языка: найти такое целое k, что язык L(G) является языком типа k и не является языком k+1.
2. Среди правил грамматик G1 и G2 найти и вычеркнуть одно правило (альтернативу) так, чтобы G1 и G2 стали эквивалентными. Ответ обосновать.
G1: S +S+Q | +R+ G2: S +V+ | +W | +S
P ε Y Y+ | – | YS
R QR | QS | R+ W –V | –W–VY | ε
Q –P
3. Дана ДС конечного автомата.
а) Построить по ней соответствующую леволинейную грамматику.
б) Если заданный автомат недетерминирован, преобразовать его в соответствии с алгоритмом преобразования НКА в эквивалентный ДКА.
в) По ДКА построить праволинейную грамматику.
+
+–
–
+–
–
+
| 4. | И |
меется клетчатый лист бумаги, бесконечный вправо и вверх. В левом нижнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {a, d, q}: a — переместить перо на одну клетку вправо;d — переместить перо по диагонали на одну клетку влево-вверх;
q — переместить перо на одну клетку вниз.
Например, по последовательности aaaaadddddqqqqq интерпретатор
построит прямоугольный равнобедренный треугольник с боковой
стороной длины 5 (см. рисунок).
Построить грамматику с терминальным алфавитом {a, d, q}, описывающую
подобные изображенному на рисунке треугольники с боковой стороной длины n, n 1. В грамматике должно быть не более 4 правил вывода (считая альтернативы).
| 5. Дана однозначная КС-грамматика Gparenthesis, порождающая язык L сбалансированных скобочных систем. Неделимой называется скобочная система, которую нельзя представить в виде конкатенации двух других скобочных систем. Например, цепочка (( )( )) – неделимая скобочная система. Протяжением скобочной системы называется число неделимых систем, конкатенация которых дает данную систему. Например, цепочка (( )( )) имеет протяжение 1, а цепочка (( )( )( ))( ) имеет протяжение 2. Пустая цепочка имеет протяжение 0. Вставить в грамматику действия вида cout << ′символ′ ; так, чтобы в процессе рекурсивного спуска был реализован перевод = {(x, 1f(x)) | x L , f (x) – протяжение цепочки x }. | Gparenthesis: S ( A ) S | A ( A ) A | |
6. Дать определение и пояснить понятие «прохода компилятора». Как это понятие связано с понятием «фазы компиляции»?
7. Что является объектом оптимизационных преобразований в компиляторах? Укажите не менее трех видов машинно-независимых оптимизационных преобразований и приведите примеры каждого из них.
8. По заданной грамматике G = {{0, 1}, {A, S}, P, S} получить эквивалентную неукорачивающую контекстно-свободную грамматику (использовать алгоритм устранения правил с пустой правой частью).
P: S 0A1 | A
A 0A | 1A |
9. Дана грамматика G. Примени́м ли к ней метод рекурсивного спуска? Ответ обосновать.
G: S dSbS | Y
Y cSY | ad | ε
10. По приведенной обратной польской записи фрагмента программы, написанной на языке Си++, восстановите этот фрагмент двумя способами: сначала, пользуясь операторами условного и безусловного перехода на метку, а затем (если это возможно), пользуясь только операторами структурного программирования без переходов. Операция ПОЛИЗ '@' соответствует унарной операции изменения знака.
| ПОЛИЗ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| a | 33 | !F | &a | &a | b | 8 | — | 7 | * | b | a | @ | 23 | / | / | — | = | += |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| ; | &b | #+ | a | b | — | < | 31 | !F | 4 | ! | 40 | ! | &b | &a | &b | +# | /= | = | ; |
|
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
