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

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

Номер 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) множество пустых чисел счетное

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