$f(x)->y$  
Не все преобразователи информации выполняют функциональное отображение информации. Результат преобразования "вход-выход" часто зависит не только от того, какая информация появилась в данный момент на входе, но и от того, что происходило раньше, то есть от предыстории преобразования.  
**Пример:** поведение человека в автобусе, которому несколько раз наступили на ногу.  
Таким образом существуют преобразователи информации, реакция которых зависит не только от входа, но и от входной истории. Такие преобразователи называются **автоматами**.  
На множестве предысторий вводится **отношение эквивалентности**: две предыстории считаются эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Таким образом, автомату достаточно запомнить класс эквивалентности, к которому принадлежит данная предыстория. Простейший случай - когда количество классов эквивалентности конечно, соответствующая формальная модель называется **конечным автоматным преобразователем** (**конечным автоматом** или **КА**).  
**Состоянием автомата** называется класс эквивалентности его входных историй. Неформально, состояние автомата - это характеристика, однозначно определяющая его дальнейшее поведение и все последующие реакции автомата на внешние события.  
Так как состояние представляет собой класс эквивалентности его входных историй, то оно может изменяться только при приходе очередного входного символа. При этом конечный автомат не только выдаёт информацию на выход, но и меняет своё состояние.  
Будущее поведение автомата определяется текущим состоянием, но не тем, как автомат в него пришёл.  
**Конечный автомат** - это устройство, работающее в дискретные моменты времени (такты); на вход КА в каждом такте поступает один из возможных входных сигналов, а на выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала. Внутреннее состояние автомата также меняется.  
**Графическое представление конечного автомата:**  
![Графическое представление конечного автомата](../Pictures/02_01.%20Графическое%20представлениее%20конечного%20автомата.png)  
**Строение конечного автомата:**  
![Строение конечного автомата](../Pictures/02_02.%20Строение%20конечного%20автомата.png)  
Текущее состояние $S$ хранится в блоке памяти (БП). Это состояние $S$ и входной символ $x$ определяют выходную реакцию автомата $y$.  
![Переход из одного состояния в другое](../Pictures/02_03.%20Переход%20из%20одного%20состояния%20в%20другое.png)  
КА может быть задан в виде ориентированного графа, где вершины графа - это состояния $S_i$, $S_j$; рёбра графа - входные $x$ и выходные $y$ сигналы.  
Входное состояние обозначается $x/y$ и проводится, когда автомат из состояния $S_i$ под воздействием входного сигнала $x$ переходит в состояние $S_j$ с выходной реакцией $y$.  
На практике получили распространение две основные модели функционирования абстрактных автоматов: модель Мили и модель Мура.
## Модель автомата Мили
Моделью автомата Мили называется шестерка компонентов следующего вида: $A=(X,Y,S,S_0,δ,λ)$, где
- $X$ - конечное непустое множество входных сигналов (входной алфавит)
- $Y$ - конечное непустое множество выходных сигналов (выходной алфавит)
- $S$ - конечное непустое множество состояний
- $S_0$ - начальное состояние, $S_0 \in S$
- $δ$: $S \times X→S$ - функция переходов
- $λ$: $S \times X→Y$ - функция выходов
  
Закон функционирования автомата Мили выглядит следующим образом:
$$S(t+1)=δ(S(t),X(t))$$
$$Y(t)=λ(S(t),X(t))$$
где $t$ - текущий момент времени, $t+1$ - следующий момент времени, $S(t)$, $X(t)$, $Y(t)$ - элементы описания автоматов в текущий момент времени.  
В модели Мили выходной сигнал явно зависит от состояния и входного символа.  
#### Пример: автомат "Продавец газет"
Автомат "Продавец газет" может получать монеты достоинством 5 и 10 рублей. Если сумма монет в автомате равна 15 рублям, автомат выдаёт газету. Если сумма больше 15 рублей, автомат возвращает деньги. Построить модель автомата Мили для этого автомата.  
$X$:  
- $x_5$ - опущена монета 5 рублей
- $x_{10}$ - опущена монета 10 рублей
  
$Y$:  
- $y_3$ - выдача газеты 
- $y_4$ - возврат денег 
- $y_5$ - сообщение "принята сумма 5 рублей" 
- $y_{10}$ - сообщение "принята сумма 10 рублей" 
$S$:  
- $S_0$ - принята сумма 0 рублей 
- $S_5$ - принята сумма 5 рублей 
- $S_{10}$ - принята сумма 10 рублей 
$δ$:  

| $X$ \ $S$ | $S_0$    | $S_5$    | $S_{10}$ |
| --------- | -------- | -------- | -------- |
| $x_5$     | $S_5$    | $S_{10}$ | $S_0$    |
| $x_{10}$  | $S_{10}$ | $S_0$    | $S_0$    |
  
$λ$:  

| $X$ \ $S$ | $S_0$    | $S_5$    | $S_{10}$ |
| --------- | -------- | -------- | -------- |
| $x_5$     | $y_5$    | $y_{10}$ | $y_3$    |
| $x_{10}$  | $y_{10}$ | $y_3$    | $y_4$    |
  
Автомат Мили может быть представлен в виде ориентированного графа:  
![Граф автомата Мили "продавец газет"](../Pictures/02_04.%20Граф%20автомата%20Мили%20Продавец%20газет.png)  
Выдача газеты ($y_3$): $(x_5, x_5, x_5) ∧ (x_5, x_{10}) ∧ (x_{10}, x_5)$ - $E_1$  
Возврат денег ($y_4$): $(x_{10}, x_{10}) ∧ (x_5, x_5, x_{10})$ - $E_2$  
$E = E_1 ∨ E_2$  
Имея формальное описание автомата Мили, можно вычислить реакцию автомата на любую входную последовательность.  
Протокол работы автомата Мили:  

| $t$ | 0     | 1        | 2        | 3        | 4     | 5        | 6        | 7        | 8        | 9        | 10       | 11    |
| --- | ----- | -------- | -------- | -------- | ----- | -------- | -------- | -------- | -------- | -------- | -------- | ----- |
| $X$ | $x_5$ | $x_{10}$ | $x_{10}$ | $x_5$    | $x_5$ | $x_5$    | $x_{10}$ | $x_{10}$ | $x_5$    | $x_{10}$ | $x_{10}$ |       |
| $S$ | $S_0$ | $S_5$    | $S_0$    | $S_{10}$ | $S_0$ | $S_5$    | $S_{10}$ | $S_0$    | $S_{10}$ | $S_0$    | $S_{10}$ | $S_0$ |
| $Y$ | $y_5$ | $y_3$    | $y_{10}$ | $y_3$    | $y_5$ | $y_{10}$ | $y_4$    | $y_{10}$ | $y_3$    | $y_{10}$ | $y_4$    |       |
  
Программная реализация автомата Мили (псевдокод):  
```
case s of //должен быть использован оператор выбора (switch)
	0: 
		if x=x5 go to S5
		if x=x10 go to S10
		else err
	5:
		if x=x5 go to ...
		if x=x10 go to ...
		...
	10: ...
def
```
Режимы: автоматический и пошаговый  
Интерфейс программы:  
![Интерфейс программы](../Pictures/02_05.%20Интерфейс%20программы.png)  
## Модель автомата Мура
$A=(x,y,S,S_0,δ,λ)$  
Закон функционирования:  
$$S(t+1)=δ(S(t), x(t))$$$$y(t)=λ(S(t))$$
Выходной сигнал модели автомата Мура явно зависит только от состояния, а косвенно от его входного символа.  
![Графы эквивалентных автоматов Мили и Мура](../Pictures/02_06.%20Графы%20эквивалентных%20автоматов%20Мили%20и%20Мура.png)  
## Преобразования автоматов
Два автомата называются **эквивалентными**, если они реализуют одинаковые отображения входных слов в выходные на всей области определения отображения.  
#### Преобразование автомата Мили в автомат Мура
*Замечания:*
1) Преобразование возможно, когда в графе автомата Мили не существует вершин, в которые бы не входила ни одна дуга
2) Каждое состояние должно иметь хотя бы одну выходящую дугу
  
![Преобразование автомата Мили в автомат Мура](../Pictures/02_07.%20Преобразование%20автомата%20Мили%20в%20автомат%20Мура.png)  
Число состояний в автомате Мура в среднем больше, чем число состояний в автомате Мили.  
$S=(S_j,y_m), (S_j,y_t), (S_j,y_l)$  
![Преобразование автомата Мили в автомат Мура](../Pictures/02_08.%20Преобразование%20автомата%20Мили%20в%20автомат%20Мура.png)  
**Пример:** построение автомата Мура, эквивалентного автомату Мили "Продавец газет":
![Граф автомата Мура "продавец газет"](../Pictures/02_09.%20Граф%20автомата%20Мура%20Продавец%20газет.png)  
## Домашнее задание
1) Построить автомат Мили, описывающий работу электронных часов с 2 кнопками:
	- $a$ - смена режима
	- $b$ - увеличение на 1
2) Построить граф автомата Мили
3) Построить эквивалентный автомат Мура