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

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

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

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