Лабораторная работа № 4. Преобразователь недетерминированного конечного автомата в детерминированный.

1. Как называется конечный автомат, у которого имеется, по крайней мере, две различные команды и при одних и тех же a и q?

• Конечный автомат

• Детерминированный конечный автомат

• Недетерминированный конечный автомат

2. Если в графе переходов недетерминированного автомата имеется хотя бы один маршрут, ведущий из начального состояния в конечное, и каждый раз, проходящий по ребру, помеченному очередным символом входной цепочки, то входная цепочка …?

• Принимается автоматом

• Не принимается автоматом

• Зацикливается автоматом

3. Программа или часть программы, выполняющая лексический анализ?

• Лексический анализатор

• Синтаксический анализатор

• Семантический анализатор

4. Структура данных, в которой доступ к элементам организован по принципу LIFO?

• Очередь

• Стек

• Список

5. Можно ли кодировочную таблицу для перевода нетерминальных символов в минимальную кодировку представить в виде массива?

• Да

• Нет

• Только с терминальными символами

6. К каким классам относят языки, для которых можно построить конечно-автоматный распознаватель?

• К регулярным

• К формальным

• К естественным

7. Алгоритм, который указывает несколько путей обработки одних и тех же входных данных, без какого-либо уточнения, какой именно вариант будет выбран?

• Детерминированный алгоритм

• Недетерминированный алгоритм

• …

8. Можно ли недетерминированный конечный автомат преобразовать в детерминированный конечный автомат?

• Да

• Нет

• Не всегда

9. Недетерминированные алгоритмы являются …?

• Случайными алгоритмами

• Вероятностными алгоритмами

• Алгоритмами, которые могут находиться одновременно во многих состояниях

10. Сколько финальных состояний может содержать недетерминированный конечный автомат?

• Одно состояние

• Множество состояний

• Не имеет финальных состояний

Раздел 3. Контекстно-свободные языки Лабораторная работа № 5. Синтаксический анализатор инфиксных арифметических выражений, основанный на методе нисходящего разбора.

1. Как называется язык, который задан КС-грамматикой?

• контекстно-свободный язык

• контекстный язык

• свободный язык

2. Частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами?

• Автоматная

• Контекстно-свободная

• Контекстно-зависимая

3. Тип 2 грамматики по иерархии Хомского называется?

• Автоматная

• Контекстно-свободная

• Контекстно-зависимая

4. Задача синтаксического анализа применительно к формальной грамматике состоит в построении…?

• Стека

• Синтаксического дерева

• Очереди

5. Как в синтаксическом анализе при методе нисходящего разбора строится дерево?

• “Cверху –вниз”

• “Снизу-вверх”

• “Слева-направо”

6. Может ли каждый очередной шаг построения дерева быть отменен последующими шагами (при нисходящем разборе)?

• Да

• Нет

• Не всегда

7. Последовательность лексем (терминалов)?

• Цепочка

• Ветвь

• Алгоритм

8. Если в недетерминированном КА n - состояний, то в соответствующем ДКА число состояний будет …?

• 2ⁿ-1

• N²

• 2ⁿ+1

9. Что значит упростить конечный автомат?

• Удалить повторяющиеся состояния

• Удалить все состояния, которые недоступны изначально

• Преобразовать в цепочку

10. Как называется ориентированный граф, вершины которого – состояния автомата, а дуги помечены элементами алфавита?

• Диаграммой переходов

• Графиком

• Диаграммой циклов