Инструменты пользователя

Инструменты сайта


examination:tyap:practice

k1) Тут не услышал в начале…

Например записано определение многочлена от одной переменной Первый вопрос заключается в том «Что означают целые коэффициенты (их может быть бесконечно много). В каком виде их записывать? Язык имеет конечное число символов в алфавите, значит надо определиться с какими именно символами надо работать. Он предполагает, что это целые числа, записанные десятичными знаками (0-9). Также знаки (+\-). Теперь: многочлен, это же степень X. Тут написано, что Х в степени n надо записывать как x^n Дальше может быть вопрос: «В каком смысле понимать многочлен?» Можно его понимать как сумму одночленов. Можно понимать как упорядоченную последовательность по убыванию степеней, а может и по возрастанию

2) Задано 4 грамматики
Надо определить, к какому типу иерархии Хомского относится каждая из них.
(Простейшая задача, все определяется по внешнему виду)

3) Построить какую-нибудь регулярную грамматику, эквивалентную грамматике с фразами (Надо догадаться, какой язык она задает (эта грамматика) и записать его с помощью правил регулярной грамматики. Можно нарисовать автомат

4) Определить КС грамматику для данного языка.
Это множество цепочек (1^b, 0^n, 1^m, 0^m)
Довольно простая задача

5) Доказать неоднозначность грамматики
Построить два разных дерева

6) Удалить бесполезные символы в грамматике с правилами
(Только недостижимые \ непродуктивные)

7) Отдельная задачка на удалене epsilon правил

8) Привести к нормальной форме Хомского.
Эту можно заменить

9) Построить регулярную грамматику, пораждающую все цепочки алфавита AB (или ab, хз), в которых символ «а» не встречается 2 раза подряд
Задачу проще решать, зарисовав автомат регулярной грамматики

10) Построить конечный автомат входного алфавита AB, который допускает такую последовательность(?) цепочек, в которой за каждое вхождение пары «аа» следует «b»

11) Построить детерминированный конечный автомат, распознающий язык грамматики.
Дана КС грамматика. На входе получится детерминированный автомат, его не надо будет переделывать

12) Определить, является ли следующий автомат минимальным.
Нарисован какой-то автомат, надо опеределить - минимальный он или нет
«Минимизация чем отличается: вы строите конгруенцию. В первой конгруенции она всего 2 класса. Второй шаг - вы разбиваете эти классы и если они у вас на втором же шаге распадутся на все одноэлементные ну вот вам и не минимизируется, а если… ну скорее всего так оно и будет»

13) По дереву разбора цепочки написать правосторонний вывод. (Типо простейшая задача)
Дано дерево разбора какой-то цепочки. Сама грамматика тут не выписана, но по дереву видно по каким правилам применялось.

14) Является ли грамматика S - Q грамматикой.
Тут надо уметь вычислять First, Follow

15)Дальше на LR грамматику.
То же, что делали в РГЗ (табличку)

16) Устранить левую рекурсию.
Дна простая грамматика

17) Выписать множество LR(0) грамматики

18) Нарисована таблица с состояниями. Дальше, если вы помните, как мы вычисляли состояния (функция goto). Тут всего-лишь один столбец (следующий) надо заполнить (после i) и все, больше ничего не надо. Показать, что вы умеете функцию goto вычислять

19) Найти схему перевода, осущ-щуу перевод булевых выражений, построенных из переменных A, B (кажется, дальше что-то типо связанных коньюнкцией и дизъюнкцией) и круглых скобок в безскобочную постфиксную

20) Дана грамматика, надо просто вычислить таблицу с отношениями Веббера и сказать после этого - является она грамматикаой простого предшествия или нет

examination/tyap/practice.txt · Последние изменения: 2014/01/15 08:23 (внешнее изменение)