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

Упражнение 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

Если количество вершин в самом длинном пути равно 4, то длина кроны дерева вывода равна

Ответ:

(1) 4

(2) 8

(3) 16

Номер 2

Если длина кроны равна 32, то количество вершин в самом длинном пути равно

Ответ:

(1) 6

(2) 7

(3) 8

Номер 3

Количество вершин в самом длинном пути, равное пяти соответствует длине кроны

Ответ:

(1) 8

(2) 32

(3) 64

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

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