Автоматы Мура и Мили

Абстрактные автоматы

{{ |definition= Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором [math]S=(A, Z, W, δ, λ, a_{1})[/math], где

1. [math]A=\{a_{1}, …, a_{m}, …, a_{M}\}[/math] - множество состояний или алфавит состояний АА.

2. [math]Z=\{z_{1}, …, z_{f}, …, z_{F}\}[/math] - множество входных сигналов или входной алфавит АА.

3. [math]W=\{w_{1}, …, w_{g}, …, w_{G}\}[/math] - множество выходных сигналов или выходной алфавит АА.

4. δ - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> ([math]a_{m}[/math], [math]z_{f}[/math]) ставит в соответствие состояние АА [math]a_{s}[/math], т.е. [math]a_{s} = δ(a_{m}, z_{f})[/math], [math]a_{s}∈A[/math].

5. λ - функция выходов АА, которая некоторым парам \<состояние – входной сигнал\> ([math]a_{m}[/math], [math]z_{f}[/math]) ставит в соответствие выходной сигнал АА [math]w_{g}[/math], т.е. [math]w_{g}=λ(a_{m},z_{f})[/math], [math]w_{g}∈W[/math].

6. [math]а_{1}[/math] - начальное состояние АА. }}

Определение:

Пусть [math]A=\{a_{1},a_{2},...,a_{n}\}[/math] — алфавит из n различных символов, [math]W=\{w_{1},w_{2},...,w_{n}\}[/math] — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов [math]C=\{c_{1},c_{2},...,c_{n}\}[/math], такой, что: 1. [math]c_{i}[/math] не является префиксом для [math]c_{j}[/math], при [math]i \ne j[/math] 2. Сумма [math]\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}[/math] минимальна. ([math]|c_{i}|[/math] — длина кода [math]c_{i}[/math]) называется кодом Хаффмана.