Книги и конспекты / Шпоры / 24
.pdf24 Конечные автоматы. Принцип работы. Покрытие автоматов. Эквивалентность автоматов. Морфизм, эпиморфизм, изоморфизм. Лемма об эпиморфных автоматах.
Конечный автомат – набор их 5 объектов |
. Здесь |
– входные символы (входной алфавит), |
|
– множество внутренних состояний, |
|
– множество выходных символов (выходной алфавит), |
|
– функция перехода (в следующее состояние), |
|
– функция выхода |
|
Автоматы задают в виде таблицы. Например, если |
, то с помощью функций |
перехода и выхода автомат M может быть задан в следующем виде: |
|
Или таблицей:
Q |
|
|
|
F |
|
0 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
1 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
0 |
|
|
|
|
Эту таблицу следует понимать следующим образом. В первой колонке перечислены элементы множества Q. В |
||||||||||||||||||||||||||||||||
первой строке перечислены элементы входного алфавита X. Во второй колонке таблицы задана функция |
||||||||||||||||||||||||||||||||
перехода F, а в третей – функция выхода . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
Если на вход автомата поступает последовательность входных символов |
|
|
|
, то автомат, начинающий работу |
||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||
из состояния |
под действием входного символа 0, переходит в состояние |
, а на выходе появляется символ 0. |
||||||||||||||||||||||||||||||
Под действием входного символа 1 из состояния |
|
автомат переходит в состояние |
и на выходе появляется 0. |
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Автомат |
покрывает |
и можно записать |
, если входной алфавит и выходной алфавиты у этих автоматов |
|||||||||||||||||||||||||||||
общие и существует функция |
|
|
, такая, что для любого положительного числа |
: |
|
|
|
|||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||
при всех |
|
|
|
|
(*). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Автоматы |
|
и |
эквивалентны ( |
|
|
), если |
|
и |
, т. е. кроме функции со свойством (*) существует |
|||||||||||||||||||||||
функция |
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Морфизмом называется такое отображение |
|
, что |
|
|
|
|
|
|
|
и |
|
|
|
|
для |
|||||||||||||||||
всех |
и |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Если отображение сюръективно, то оно – эпиморфизм, если |
биективно, то оно изоморфизм. |
|||||||||||||||||||||||||||||||
Лемма. Пусть |
– эпиморфизм автомата на . Тогда для любой входной строки |
|
|
|
|
|
|
и |
||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||
начального состояния |
|
выходная строка |
|
|
|
|
|
|
автомата |
совпадает с выходной строкой |
||||||||||||||||||||||
|
|
|
|
|
|
|||||||||||||||||||||||||||
автомата , если начальное состояние автомата |
|
равно |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
Доказательство. Проводится индукцией по . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|