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

Упражнение 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) может разрешать язык

(2) не может разрешать язык

(3) не работает с языками

Упражнение 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) перечислимым

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