Теория автоматов. Определение конечного автомата

1. Теория автоматов

Определение конечного
автомата

2. Понятие автомата

Автомат – это математическая модель
устройства, обрабатывающего дискретную
информацию с помощью заданного алгоритма,
не учитывающая физические и технические
характеристики этого устройства
Устройство обменивается информацией с
внешней средой с помощью входного и
выходного каналов. Информация, поступающая
через входной канал называется входными
сигналами; передаваемая через выходной
канал – выходными сигналами
Устройство имеет память, содержимое которой
может меняться во время работы устройства

3. Понятие автомата

Содержимое памяти будем называть
состоянием автомата
Поведение устройства в каждый момент
времени зависит от входных сигналов и
содержимого памяти
Поведение устройства определяет, какой будет
сформирован выходной сигнал и каким станет
содержимое памяти
Поведение устройства описывается некоторыми
правилами

4. Понятие автомата

Устройство действует дискретно: через
одинаковые фиксированные промежутки
времени (называемые тактами) одновременно
происходит несколько событий:
поступает
очередной входной сигнал;
считывается текущее состояние автомата;
на основе правил функционирования устройства
определяется новое состояние автомата и выходной
сигнал;
новое состояние запоминается, выходной сигнал
отправляется
В остальное время устройство бездействует

5. Схема автомата

Такты длятся 1 единицу времени, т.е. все
события происходят в моменты времени
t=1,2,3,…
вход. входной
сигнал канал
Функциональный блок
(правила функционирования)
текущее
состояние
новое
состояние
Память
выходной вых.
сигнал
канал

6. Формализация

Множество возможных входных сигналов
назовем входным алфавитом
A a1 , a2 , , as
Множество возможных выходных сигналов
назовем выходным алфавитом
B b1 , b2 , , bk
Множество возможных состояний устройства
назовем множеством состояний
V v1 , v2 , , vr

7. Формализация

Входной сигнал в момент времени t будем
обозначать x(t)
Выходной сигнал в момент времени t – y(t)
Текущее состояние в момент времени t – q(t-1)
Новое (формируемое) состояние автомата в
момент времени t – q(t)
x(t ) A, y (t ) B, q(t 1) V , q(t ) V
Функционирование автомата начинается с
момента времени t = 1

8. Схема автомата

x(t)
входной
канал
Функциональный блок
(правила функционирования)
q(t-1)
выходной
канал
q(t)
Память
Состояние q(0) – начальное состояние
автомата.
Автомат называется инициальным, если для
него задано начальное состояние
y(t)

9. Детерминированные автоматы

Правила для определения y(t) и q(t), вообще
говоря, ничем не ограничиваются
(утверждается только, что они могут зависеть
от x(t) и q(t-1))
Автоматы, в которых y(t) и q(t) при известных
x(t) и q(t-1) определяются однозначно,
называются детерминированными
Более формальное определение:
автомат называется детерминированным, если
для любых моментов времени t, t’ из равенств
x(t ) x(t ), q(t 1) q(t 1)
следуют равенства y (t ) y (t ), q(t ) q(t )

10. Пример

A={a1,a2,a3} B={b1,b2,b3} V={v1,v2}
Правила функционирования:
(a1,v1)→(b1,v1), (a2,v1)→(b2,v1), (a3,v1)→(b3,v2)
(a1,v2)→(b1,v2), (a2,v2)→(b1,v1), (a3,v2)→(b3,v2)
Что будет на выходе, если на вход подается
последовательность a2, a3, a2?
выход: b2
q(0) = v1
состояния:
выход: b
v11
если q(0) = v2
v
если
состояния:
Данный
1
b3
bv3
2
v2
b1
bv1
1
v1
автомат может быть моделью реального «устройства»
- «идеальной кошки»
a1 – погладить a2 – накормить a3 – наказать
b1 – мурлыкает b2 – умывается b3 – прячется под диван
v1 – кошка довольна v2 – кошка нервничает

11. Формализация

Функцией выходов называется функция f,
которая каждой паре (ai,vj), где ai=x(t) A,
vj=q(t-1) V ставит в соответствие выходной
сигнал f(ai,vj)=y(t) B
Функцией переходов называется функция g,
которая каждой паре (ai,vj), где ai=x(t) A,
vj=q(t-1) V ставит в соответствие новое
состояние g(ai,vj)=q(t) V
Данные понятия, очевидно, могут быть введены
только для детерминированного автомата,
поскольку само определение функции означает,
что y(t) и q(t) вычисляются однозначно

12. Заключительные состояния

F – множество заключительных состояний, F V
V \ F – множество не заключительных состояний
Если на вход инициальному автомату подана
x x(1), x(2), x(T )
последовательность ~
и автомат закончил работу в состоянии v F, то
говорят что автомат принимает (распознает)
последовательность ~x
Работа автомата не останавливается при
достижении заключительного состояния, а
продолжается до тех пор, пока не закончится
последовательность входных сигналов

13. Формальное определение

Конечным детерминированным автоматом
(автоматом Мили) называется система из
шести компонент (A, B, V, F, f, g), где
– входной алфавит
B – выходной алфавит
V – множество состояний
F – множество заключительных состояний
f – функция выходов
g – функция переходов,
причем множества A, B, V – конечны
A

14. Теория автоматов

Способы задания
автоматов Мили

15. Способы задания автоматов

1.
2.
3.
Набор правил
Таблица выходов и переходов
Диаграмма Мура

16. Таблица выходов и переходов

v1
…
vr
a1
f(a1,v1),g(a1,v1)
…
f(a1,vr),g(a1,vr)
…
…
…
…
as
f(as,v1),g(as,v1)
…
f(as,vr),g(as,vr)
Заключительные состояния помечаются
символом «*»: если vi F, то в таблице оно
*
будет записано как vi
Начальное состояние помечается символом

17. Пример

A={a1,a2,a3} B={b1,b2,b3} V={v1,v2}
(a1,v1)→(b1,v1), (a2,v1)→(b2,v1), (a3,v1)→(b3,v2)
(a1,v2)→(b1,v2), (a2,v2)→(b1,v1), (a3,v2)→(b3,v2)
v1
v2
a1
(b1,v1)
(b1,v2)
a2
(b2,v1)
(b1,v1)
a3
(b3,v2)
(b3,v2)

18. Способы задания автоматов

1.
2.
3.
Набор правил
Таблица выходов и переходов
Диаграмма Мура

19. Диаграмма Мура

Диаграмма Мура – это ориентированный
мультиграф с петлями G(VG, EG)
Множество вершин – это множество состояний
VG=V
Дуга (vi , v j ) EG al A : g a l , vi v j
при этом дуга помечается парой (al, f(al, vi))
Как и в табличном задании, заключительные
состояния помечаются символом *, а начальное
состояние – символом
Условие детерминированности: из каждой
вершины выходит ровно s дуг: по одной для
каждого входного сигнала

20. Пример

A={a1,a2,a3} B={b1,b2,b3} V={v1,v2}
(a1,v1)→(b1,v1), (a2,v1)→(b2,v1), (a3,v1)→(b3,v2)
(a1,v2)→(b1,v2), (a2,v2)→(b1,v1), (a3,v2)→(b3,v2)
(a1,b1)
(a1,b1)
(a3,b3)
(a2,b1)
(a2,b2)
v2
v1
(a3,b3)

21. Представление нескольких входов/выходов

Входной сигнал может быть вектором:
Выходной сигнал также может быть вектором:
Как правило, компоненты вектора однотипны,
то есть принадлежат одному множеству,
поэтому входным (выходным) алфавитом
будем считать не множество всех возможных
векторов, а множество возможных значений
компонент вектора:
x(t ) x1 (t ), x2 (t ), , xn (t )
y(t ) y1 (t ), y2 (t ), , ym (t )
xi (t ) A, i 1..n, y j (t ) B, j 1..m

22. Представление нескольких входов/выходов

Функции выходов и переходов примут вид:
q(t ) g ( x(t ), q(t 1)) g x1 (t ), x2 (t ), , xn (t ), q(t 1)
y1 (t ) f1 ( x(t ), q(t 1)) f1 x1 (t ), x2 (t ), , xn (t ), q(t 1)
...
ym (t ) f m ( x(t ), q(t 1)) f m x1 (t ), x2 (t ), , xn (t ), q(t 1)
В табличном задании автомата в строках будут
перечисляться всевозможные вектора, в
ячейках вместо одного выходного значения
будет записываться выходной вектор
В диаграмме Мура на дугах также будут
подписываться вектора

23. Пример2

A=B={0, 1} V={0, 1} n = 2, m = 1
(00,0)
(01,0)
(00,1)
(01,1)
(10,0)
(11,1)
(10,1)
0
Пусть
1
(11,0)
T T 1 2 1 , T T 1 2 1
x1 (t ) t , x2 (t ) t
Тогда на выходе получим:
y(T ) y(T 1) y(2) y(1) : (mod 2T )

24. Теория автоматов

Следующая тема:
Теория автоматов
Типы автоматов Мили