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

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

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