ИДЗ-2 МЛиТА-2014

Задания по ИДЗ-2 МлиТА 2014

Работы должны быть выложены на студенческих сайтах в форме документов, к редактированию которых преподаватель имеет доступ.
В отчёт должны войти:
1. Набор граничных примеров и контрпримеров, демонстрирующих уточнение языка.
2. КС-грамматика языка.
3. Грамматический разбор одного примера.
4. Проверка того, что грамматика удовлетворяет однозначности ветвления по первому символу (принадлежит классу LL0).
5. Модифицированная грамматика (если исходная КС-грамматика не удовлетворяет условию однозначности ветвления).
6. Таблица перевода языка в диаграммы (может быть опущена, если используется алгоритм прямого перевода, который должен быть сформулирован вместо диаграмм) (располагать материалы в два столбика так, чтобы на экране можно было видеть  одновременно соответствующие части грамматики и диаграммы). Оптимизация числа диаграмм подстановкой. 
7. Таблица перевода синтаксических диаграмм в алгоритм синтаксического анализа (располагать материалы в два столбика так, чтобы на экране можно было видеть  одновременно соответствующие части алгоритма и диаграммы).
8. Таблица перевода алгоритма в программу (располагать материалы в два столбика так, чтобы на экране можно было видеть  одновременно соответствующие части алгоритма и программы).
9. Исходный код программы.
10. Исполняемый файл программы (при запуске программы должно появляться условие задачи с примерами и инструкция по вводу, после выполнения программа должна предложить ввести другой пример выражения для анализа).

ИДЗ-2 Задания по теме «Языки и грамматики» (всего 22 темы)


1. Лабиринт.

Робот движется по лабиринту, находит сокровище T и возвращается по тому же пути обратно. Нужно описать язык протоколов движения робота. Например, UURULLTRRDLDD. U — шаг вверх, D — шаг вниз, R — шаг вправо, L — шаг влево


2. Обход бинарного дерева. Описать язык путей обхода произвольных бинарных деревьев, показанный рисунком.

Пример: LU LU RD RU LU RD RU LD LD RD


3. Неубывающие цифры. Натуральные числа в шестнадцатеричной записи, цифры которых идут в неубывающем порядке. Примеры правильных записей: 135AD, 222222ADEEEEE.


4. Пути в графе, определенные как последовательности рёбер. Ребро определяется парой вершин. Каждая вершина именуется двумя натуральными числами. Первое используется для именования вершины, в которую входит ребро, число из этих же цифр в обратном порядке — для наименования этой же вершины, когда ребро из неё выходит. Для упрощения будем рассматривать числа только из цифр {0; 1; 2}. Пример правильной записи пути:

(12;201) (102;1) (1; 2012) (2102; 11). Имена вершин не могут начинаться с 0.


5. Работа стека. При вычислении значений формул в постфиксной записи используется стек. Пусть стек имеет 4 ячейки и на каждом шаге его содержимое либо увеличивается, либо уменьшается на 1 элемент. Опишите язык последовательностей заполнения стека. Пример правильной записи:

1;2;1;2;3;4;3;4;3;2;3;4;3;2;1

Начинается и завершается запись с 1.


6. «Финский» язык. Слово не может начинаться с двух согласных. Подряд не могут идти более двух гласных, также и более двух согласных. Слово заканчивается на гласную. В слове не может быть более одной пары одинаковых согласных подряд, то же и про гласные (условие удалено, чтобы уменьшить сложность задачи)Пары одинаковых гласных и согласных не могут идти подряд.

Примеры правильных слов (букв можно взять минимум 4-6):

ТААКОТТО, КААТОО, КОАККО


7*. Базовые регулярные выражения POSIX (найти информацию самостоятельно)


8 (8-1). Обход дерева в глубину 1. Вершины бинарного дерева покрашены в два цвета так, что любое ребро соединяет вершины разного цвета. Затем делается обход в глубину и последовательность цветов (КССККСКС) инвертируется: СКСККССК. Описать язык получающихся последовательностей.


9 (8-2). Обход дерева в глубину 2. Вершины бинарного дерева покрашены в два цвета так, что любое ребро соединяет вершины разного цвета. Затем букашка делает обход в глубину, при этом записывается каждая пройденная вершина, но только по одному разу, если на каком то уровне одна из ветвей отсутствует, пишется O (на рисунке получается: 

СКСКOOOСOOКOСКOOO). Описать язык получающихся последовательностей.


10 (8-3). Обход дерева в глубину 3. Вершины бинарного дерева покрашены в два цвета так, что любое ребро соединяет вершины разного цвета. Затем букашка делает обход в глубину, при этом записывается каждая пройденная вершина, но только по одному разу, если вершина является листом, то после неё пишется Л (на рисунке получается: 

СКСКЛСЛКСКЛ). Описать язык получающихся последовательностей.


11 (8-4). Обход дерева в глубину 4. Букашка делает обход дерева в глубину, при этом при движении вниз записывается направление движения (L или R), движения в обратном направлении (букашка «пятится» не записываются). На рисунке получается: LLLLRRRL. Описать язык получающихся последовательностей.


12  (9-1). Красно-черные деревья-1 (упрощенный вариант). Вершины бинарного дерева покрашены в два цвета так, что у красных вершин могут быть только черные потомки. Затем делается обход в глубину и последовательность цветов (ЧЧЧКЧЧКЧ) инвертируется: ЧКЧЧКЧЧЧ. Описать язык получающихся последовательностей.


13 (9-2). Красно-черные деревья-2 (упрощенный вариант). Вершины бинарного дерева покрашены в два цвета так, что у красных вершин могут быть только черные потомки. Затем букашка делает обход в глубину, при этом записывается каждая пройденная вершина, но только по одному разу, если на каком то уровне одна из ветвей отсутствует, пишется O (на рисунке получается: ЧКЧЧOOOЧOOКOЧЧOOO). Описать язык получающихся последовательностей.


14 (9-3). Красно-черные деревья-3 (упрощенный вариант). Вершины бинарного дерева покрашены в два цвета так, что у красных вершин могут быть только черные потомки. Затем букашка делает обход в глубину, при этом записывается каждая пройденная вершина, но только по одному разу, если вершина является листом, то после неё пишется Л (на рисунке получается:
ЧКЧЧЛЧЛКЧЧЛ). Описать язык получающихся последовательностей.


15 (10 в старой нумерации). Счастливые билеты. Язык последовательностей 0 и 1 с разделителем посередине. Сумма чисел слева и справа от разделителя одинакова и не превышает 2.

Примеры правильных записей:

00100010|11000000 01000|00001 00|00


16 (11 в старой нумерации). Вложенные предложения (слова не выделенные жирным — произвольные последовательности букв). Пример: Вот пес без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в темном чулане хранится в доме,который построил Джек.


Человек на мосту-1. Человек стоит на левом краю моста и делает шаги влево (L), вправо (R) или стоит на месте (E). Опишите язык всех передвижений, при которых он не выйдет за пределы моста. Например, RREEERLRLLL.



17 (12-2 в старой нумерации). Человек на мосту-2. Человек стоит на левом краю моста и смотрит вправо. Он может сделать шаг вперёд (S) или развернуться на 180 градусов (R). Опишите язык всех передвижений, при которых он не выйдет за пределы моста. Например, SSRRRSSRS.



18 (13-1 в старой нумерации). Люди на мосту -1. Два человека по очереди ходят вправо (R) или влево (L) так, что они не падают с моста и не сталкиваются друг с другом. Шаги записываются поочередно, то для первого, то для второго. Например, RLLLRR. Опишите язык таких последовательностей.

19 (13-2 в старой нумерации)Люди на мосту -2. Два человека по очереди ходят (S) или поворачиваются на 180 градусов (R) так, что они не падают с моста и не сталкиваются друг с другом. Шаги записываются поочередно, то для первого, то для второго. Например, SSRRRS. Опишите язык таких последовательностей.



20 (14 в старой нумерации). Неравенство чисел. Рассмотрим множество неравенств натуральных чисел из одинакового количества цифр 1 и 2. Причем цифры первого числа записываются в обратном порядке. Например,

11112<11121      2121<1222. Описать язык таких выражений.


21 (15 в старой нумерации). Сложные функции любого числа переменных. Примеры: f(x;g(x;x;y)) f(h(f(x;y;z;u)) k(f(x;y);f(x;z;x);f(f(x;y;z;u))). Описать язык таких выражений, учитывая, что одинаковые имена могут иметь функции разного числа переменных.

22 (16* в старой нумерации). Вложенные конструкции IF THEN в C++. 

Пример (обобщить):

if (a > b) {

if (a > c) cout << a;

else cout << c;

} else {

if (b > c) {

cout << b;

} else {

cout << c;

}

}



Ċ
Sergey Pozdnyakov,
16 нояб. 2014 г., 2:59
Ċ
Sergey Pozdnyakov,
22 нояб. 2014 г., 11:36
Comments