2012 вариант 1 (1119762)
Текст из файла
Вариант 1_2012 Ф.И.О.___________________________________№ группы________
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1. Дана грамматика G: S aS |Sb|aAb|ab aAb aaAbb|aabb aaAbb aaAbb aAb aAb |
(a) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы). |
(б) Каким из перечисленных классов грамматик принадлежит G? Ответ:
|
(в) Тип языка: найти такое целое k, что язык L(G) является языком типа k и не является языком k+1.
2. Среди правил грамматик G1 и G2 найти и вычеркнуть одно правило (альтернативу) так, чтобы G1 и G2 стали эквивалентными. Ответ обосновать.
G1: S aAa |aSaB G2: S aAa | aB |aS
A Aa |BA |BS Y Ya |b |YS
B bC B bA | bBC | ε
C ε C bAY
3. а) Построить по заданной грамматике G конечный автомат (в виде ДС).
б) Если автомат оказался недетерминированным, преобразовать его в соответствии с алгоритмом преобразования НКА в эквивалентный ДКА.
в) По ДКА построить леволинейную грамматику.
G: H 1A | 1B
A 0B | 1C
B 1A |
C 1A | 1C
| 4. | Имеется клетчатый лист бумаги, бесконечный вправо и вниз. В левом верхнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {a, b, с}: a — переместить перо на одну клетку вправо; | |
| b — переместить перо по диагонали на одну клетку влево-вниз; c — переместить перо на одну клетку вверх. Например, по последовательности aaaaabbbbbссссс интерпретатор построит прямоугольный равнобедренный треугольник с боковой стороной длины 5 (см. рисунок). Построить грамматику с терминальным алфавитом {a, b, с}, описывающую подобные изображенному на рисунке треугольники с боковой стороной длины n, n 1. В грамматике должно быть не более 4 правил вывода (считая альтернативы). |
| |
| 5. Дана однозначная КС-грамматика Gbalance, порождающая язык L, состоящий из цепочек, в которых символов a и b поровну: L={ x {a,b}* |x|a = |x|b }. Вставить в грамматику действия вида cout << ′′символы′′ ; так, чтобы в процессе рекурсивного спуска был реализован перевод = {(x, (ab)f(x)) | x L , f (x)= |x|a + |x|b }. | Gbalance : S aAbS |bBaS | A aAbA | B bBaB| |
6. Какие стратегии трансляции могут выбираться в различных системах программирования? Объяснить существенные отличия этих подходов к реализации процесса трансляции с языка программирования. Приведите по одному примеру формального языка, к которому применена каждая из названных вами стратегий трансляции.
7. В чём различие статических и динамических библиотек? Какие компоненты вычислительной системы занимаются подключением к программам каждого типа библиотек?
8. По заданной грамматике G = {{+, –}, {R, S}, P, S} получить эквивалентную неукорачивающую контекстно-свободную грамматику (использовать алгоритм устранения правил с пустой правой частью).
P: S +R– |
R +R | –S | S
9. Дана грамматика G. Примени́м ли к ней метод рекурсивного спуска? Ответ обосновать.
G: S aSb | Yb | bb
Y cSY | dd | ε
10. По приведенной обратной польской записи фрагмента программы, написанной на языке Си++, восстановите этот фрагмент двумя способами: сначала, пользуясь операторами условного и безусловного перехода на метку, а затем (если это возможно), пользуясь только операторами структурного программирования без переходов. Операция ПОЛИЗ '@' соответствует унарной операции изменения знака.
| ПОЛИЗ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| &a | #+ | 4 | + | b | <= | 36 | !F | &b | +# | a | b | — | < | 34 | !F | &a |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
| b | 8 | — | 7 | * | b | a | @ | 23 | / | / | — | = | ; | 9 | ! | 39 | ! | &b | 1 | = | ; |
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
