Математическая теория формальных языков

Упражнение 1:

Номер 1

Контекстно-свободным грамматикам соответствуют

Ответ:

(1) конечные автоматы

(2) автоматы с магазинной памятью

(3) бесконечные детерминированные автоматы

Номер 2

Автоматы с магазинной памятью соответствуют

Ответ:

(1) контекстно-свободным грамматикам

(2) праволинейным грамматикам

(3) как контекстно-свободным, так и праволинейным грамматикам

Номер 3

Вид автоматов, соответствующих контекстно-свободным грамматикам называется

Ответ:

(1) детерминанты

(2) конечные автоматы

(3) автоматы с магазинной памятью

Упражнение 2:

Номер 1

Автоматы бывают

Ответ:

(1) конечными

(2) аддитивными

(3) с магазинной памятью

Номер 2

Автоматы с магазинной памятью

Ответ:

(1) ничем не отличаются от конечных автоматов

(2) абсолютно отличаются от конечных автоматов

(3) являются итерационными автоматами

Номер 3

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

Ответ:

(1) отличаются от автоматов с магазинной памятью

(2) являются автоматами с магазинной памятью

(3) являются неоднородно распределяемыми аддитивными автоматами

Упражнение 3:

Номер 1

Автомат с магазинной памятью

Ответ:

(1) отличается от конечного автомата наличием потенциально бесконечной памяти

(2) отличается от конечного автомата отсутствием потенциально бесконечной памяти

(3) ничем не отличается от конечного автомата

Номер 2

Наличие потенциально бесконечной памяти характерно для

Ответ:

(1) конечного автомата

(2) автомата с магазинной памятью

(3) конечного автомата и для автомата с магазинной памятью

Номер 3

В автомате с магазинной памятью присутствует

Ответ:

(1) ограниченная память, хранящая текущее состояние

(2) потенциально бесконечная память

(3) инъективная память

Упражнение 4:

Номер 1

Потенциально бесконечная память используется

Ответ:

(1) как стек

(2) как буфер обмена

(3) посредством вывода символов в определенной последовательности

Номер 2

В роли стека в автоматах с магазинной памятью используется

Ответ:

(1) память, хранящая текущее состояние

(2) бесконечная память

(3) как память, хранящая текущее состояние, так и бесконечная память

Номер 3

Функцию магазина в автоматах с магазинной памятью выполняет

Ответ:

(1) память, хранящая текущее состояние

(2) бесконечная память

(3) как бесконечная память, так и память текущего состояния

Упражнение 5:

Номер 1

Бесконечная память представляет собой

Ответ:

(1) структуру данных

(2) последовательность символов и пустых слов

(3) многомерный массив числовых данных

Номер 2

Структура данных, где в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов, носит название

Ответ:

(1) бесконечная память

(2) память, хранящая текущее состояние

(3) аддитивно-доступная память

Номер 3

В определенный момент обработки

Ответ:

(1) доступен только один элемент бесконечной памяти

(2) доступна пара элементов бесконечной памяти

(3) доступны все элементы бесконечной памяти

Упражнение 6:

Номер 1

При формальном определении конфигурации автомата с магазинной памятью считают все содержимое стека

Ответ:

(1) конечной последовательностью символов

(2) бесконечной последовательностью символов

(3) словом

Номер 2

Порядок записи содержимого стека

Ответ:

(1) имеет значение

(2) не имеет значения

(3) не проверяется

Номер 3

Вершина стека находится

Ответ:

(1) в начале слова

(2) в конце слова

(3) справа

Упражнение 7:

Номер 1

С понятием автомата с магазинной памятью связывают

Ответ:

(1) входной алфавит

(2) алфавит магазинной памяти

(3) множество переходов

Номер 2

При определении автомата магазинной памяти используют

Ответ:

(1) множество состояний

(2) заключительные состояния

(3) допускающие состояния

Номер 3

Количество составляющих автомата с магазинной памятью равно

Ответ:

(1) 6

(2) 12

(3) 18

Упражнение 8:

Номер 1

Автоматы с магазинной памятью можно изображать с помощью

Ответ:

(1) диаграмм состояний

(2) диаграмм соответствия

(3) интерполяционных диаграмм

Номер 2

Изображение автоматов с магазинной памятью посредство диаграмм состояний

Ответ:

(1) возможно

(2) невозможно

(3) не имеет практического смысла

Номер 3

Для изображения автоматов с магазинной памятью используют

Ответ:

(1) пустые множества

(2) диаграммы состояний

(3) как пустые множества, так и диаграммы состояний

Упражнение 9:

Номер 1

Язык, распознаваемый автоматом с магазинной памятью - это

Ответ:

(1) множество всех слов, допускаемых этим автоматом

(2) множество всех слов

(3) пустое множество

Номер 2

Множество всех слов, допускаемых автоматом с магазинной памятью, формирует

Ответ:

(1) алфавит

(2) язык

(3) корреляцию символов

Номер 3

Если автоматы с магазинной памятью распознают один и тот же язык, то они

Ответ:

(1) эквивалентны

(2) аддитивны

(3) несоответственны

Математическая теория формальных языков - тест 10