Конечные автоматы
Тема 9.Теория автоматов. Основные понятия теории конечных автоматов. Способы задания абстрактных автоматов: таблица переходов, граф переходов, матрица переходов. Автоматы Мили и Мура. Частичный автомат.
Конечный автомат Мура определяется кортежем …
а)
б)
в)
г)
Конечный автомат Мили определяется кортежем …
а)
б)
в)
г)
Конечный автомат может быть задан …
а) автоматной таблицей
б) графом переходов
в) матрицей переходов
г) таблицей истинности
Число вершин в графе переходов автомата Мили определяется …
а) мощностью входного алфавита X
б) мощностью выходного алфавита Y
в) мощностью множества состояний S
г) функцией выходов λ
д) функцией переходов δ
Число вершин в графе переходов автомата Мура определяется …
а) мощностью входного алфавита X
б) мощностью выходного алфавита Y
в) мощностью множества состояний S
г) функцией выходов λ
д) функцией переходов δ
Характеристические функции λ и δ в графе переходов автомата Мили обозначают …
а)
б)
в)
г)
Характеристические функции λ и δ в графе переходов автомата Мура обозначают …
а)
б)
в)
г)
Абстрактный конечный автомат представляют …
а) черным ящиком
б) одним входом
в) одним выходом
г) комбинационной схемой
д) памятью
е) несколькими входами
ж) несколькими выходами
Структурный конечный автомат представляют …
а) черным ящиком
б) одним входом
в) одним выходом
г) комбинационной схемой
д) памятью
е) несколькими входами
ж) несколькими выходами
Эквивалентные состояния конечного автомата обладают свойствами …
а) рефлексивности
б) симметричности
в) транзитивности
г) полноты
д) антисимметричности
е) антирефлексивности
Минимизацию числа состояний абстрактного конечного автомата выполняют …
а) методом Хаффмена
б) методом Петрика
в) методом карт Карно
г) методом неопределенных коэффициентов
Автоматной таблице конечного автомата Мили
|
δ |
1 |
2 |
3 |
λ |
1 |
2 |
3 |
|
x1 |
2 |
1 |
3 |
x1 |
1 |
2 |
2 |
|
x2 |
1 |
3 |
2 |
x2 |
1 |
1 |
2 |
соответствует граф переходов …
а)
б)
в)
Автоматной таблице конечного автомата Мили
|
δ |
1 |
2 |
3 |
λ |
1 |
2 |
3 |
|
x1 |
2 |
1 |
2 |
x1 |
2 |
2 |
2 |
|
x2 |
1 |
3 |
3 |
x2 |
1 |
1 |
1 |
соответствует граф переходов …
а)
б)
в)
Алгебраические системы
Тема 4.Алгебраические системы. Понятие алгебраической системы, алгебры, модели. Группоиды и полугруппы. Понятие группы. Кольца, тела и поля. Гомоморфизм и изоморфизм. Дистрибутивные решетки. Определение решетки, дистрибутивной решетки. ЧУ-множества, диаграмма Хассе. Булева решетка.
Множество Mвместе с заданными на нем операциями Σ = {φ1,φ2, …,φn} и отношениями Ω =
называется … .
а) алгеброй
б) алгебраической системой
в) моделью
Множество Mвместе с заданными на нем операциямиφ1,φ2, …,φnназывается … .
а) алгеброй
б) алгебраической системой
в) моделью
,
гдеM‑ множество
вместе с заданными на нем операциямиφ1,φ2,
…,φn,
является обозначением … .
а) алгебры
б) алгебраической системы
в) модели
В обозначении алгебры
,
гдеM‑ множество
вместе с заданными на нем операциямиφ1,φ2,
…,φn,Мназывают … .
а) носителем
б) сигнатурой
в) порядком
В обозначении алгебры
,
гдеM‑ множество
вместе с заданными на нем операциямиφ1,φ2,
…,φn, Σ = {φ1,φ2,
…,φn}
называют … .
а) носителем
б) сигнатурой
в) порядком
В обозначении
алгебраической системы, гдеM‑ множество вместе с заданными на
нем операциями Σ = {φ1,φ2, …,φn}
и отношениями Ω =
,
Ω =
называют … .
а) носителем
б) сигнатурой
в) порядком
г) множеством отношений
Множество Mвместе с заданными на нем отношениями
называется … .
а) алгеброй
б) алгебраической системой
в) моделью
,
гдеM‑ множество
вместе с заданными на нем отношениями
,
является обозначением …
а) алгебры
б) алгебраической системы
в) модели
Примерами алгебраических систем могут служить …
а)
б)
в)
г)
Примерами алгебры могут служить …
а)
б)
в)
г)
Примерами модели могут служить …
а)
б)
в)
г)
Алгебраическая система
,
где Σ состоит из одной бинарной операции
называется …
а) группоидом
б) моделью
в) сигнатурой
г) кольцом
Группоид
,
где
и
есть
сложение по модулю 2 представлен таблицей
Кэли … .
а)
|
|
0 |
1 |
|
0 |
0 |
1 |
|
1 |
1 |
0 |
а)
|
|
0 |
1 |
|
0 |
0 |
1 |
|
1 |
1 |
1 |
а)
|
|
0 |
1 |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
а)
|
|
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
1 |
Примерами группоидов
являются … .
а)
б)
в)
г)
Группоид
называется идемпотентным, если … .
а)
б)
в)
Группоид
называется коммутативным, если … .
а)
б)
в)
Группоид
называется полугруппой или моноидом,
если … .
а)
б)
в)
Группоид
называется абелевой полугруппой, если
… .
а)
б)
в)
Отображение множества
в себя называется … .
а) подстановкой
б) композицией
в) перестановкой
Пусть
– множество всех подстановок множества
чисел {1, 2} в себя. Тогда двойка
образует группоид. Обозначим
,
.
Определить таблицу Кэли для группоида,
который вмещает все взаимно однозначные
подстановки чисел 1, 2 относительно
операции композиции
… .
а)
|
|
a |
b |
|
a |
a |
b |
|
b |
b |
a |
а)
|
|
a |
b |
|
a |
b |
a |
|
b |
a |
b |
а)
|
|
a |
b |
|
a |
a |
a |
|
b |
b |
b |
а)
|
|
a |
b |
|
a |
a |
b |
|
b |
a |
b |
Алгебра
называется группой, если удовлетворяет
условиям … .
а)
б)
в)
г)
Алгебра
называется абелевой группой, если
удовлетворяет условиям … .
а)
б)
в)
г)
Таблица Кэли абелевой (коммутативной) группы … .
а) симметрична относительно главной диагонали
б) симметрична относительно побочной диагонали
в) несимметрична относительно главной диагонали
г) несимметрична относительно побочной диагонали
Число элементов в носителе Aконечной группы
называют
ее … .
а) мощностью
б) порядком
в) длиной
г) рангом
Подмножество
,
где
группы
,
также может образовывать группу. В этом
случаеGназывается
… группы U.
а) подгруппой
б) подстановкой
в) полугруппой
Для того, чтобы непустое подмножество GгруппыUбыло подгруппой, необходимо и достаточно, чтобы … .
а)
б)
в)
г)
Алгебра
есть кольцо, если
выполняются условия … .
а)
б)
в)
г)
д)
е)
ж)
з)
Кольцо
называется абелевым, если … .
а)
б)
Кольца
,
в которых для всех отличных от нуля
элементов
существуют обратные, называются … .
а) телами
б) полями
в) группами
Если мультипликативная группа тела абелева, т. е. … , то тело называется полем.
а)
б)
Объекты, которые имеют одну и ту же форму, одинаковое назначение и, возможно, выполняют одинаковую функцию, называют … .
а) изоморфными
б) гомоморфными
в) аморфными
Два группоида
и
называются
… между собой, если существует такая
взаимно однозначная функция
,
что для всех
.
а) изоморфными
б) гомоморфными
в) аморфными
Отображение fгруппоида
на
называется … , если для всех
.
а) гомоморфизмом
б) изоморфизмом
От гомоморфизма … взаимно однозначное соответствие.
а) требуется
б) не требуется
Правильным утверждением является … .
а) любой изоморфизм является также гомоморфизмом
б) любой гомоморфизм является также изоморфизмом
При гомоморфизме
и
сохраняются свойства … алгебраической
операции.
а) коммутативности
б) ассоциативности
в) дистрибутивности
г) идемпотентности