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

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

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