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

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

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