игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Математическая теория формальных языков / Тест 3

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

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