173
правки
Изменения
Новая страница: «== Абстрактные автоматы == |definition= Абстрактный автомат (АА) является математической модел...»
== Абстрактные автоматы ==
|definition=
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, δ, λ, a_{1})</tex>, где
1. <tex>A=\{a_{1}, …, a_{m}, …, a_{M}\}</tex> - множество состояний или алфавит состояний АА.
2. <tex>Z=\{z_{1}, …, z_{f}, …, z_{F}\}</tex> - множество входных сигналов или входной алфавит АА.
3. <tex>W=\{w_{1}, …, w_{g}, …, w_{G}\}</tex> - множество выходных сигналов или выходной алфавит АА.
4. δ - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие состояние АА <tex>a_{s}</tex>, т.е. <tex>a_{s} = δ(a_{m}, z_{f})</tex>, <tex>a_{s}∈A</tex>.
5. λ - функция выходов АА, которая некоторым парам \<состояние – входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие выходной сигнал АА <tex>w_{g}</tex>, т.е. <tex>w_{g}=λ(a_{m},z_{f})</tex>, <tex>w_{g}∈W</tex>.
6. <tex>а_{1}</tex> - начальное состояние АА.
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
2. Сумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
называется '''кодом Хаффмана'''.
}}
|definition=
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, δ, λ, a_{1})</tex>, где
1. <tex>A=\{a_{1}, …, a_{m}, …, a_{M}\}</tex> - множество состояний или алфавит состояний АА.
2. <tex>Z=\{z_{1}, …, z_{f}, …, z_{F}\}</tex> - множество входных сигналов или входной алфавит АА.
3. <tex>W=\{w_{1}, …, w_{g}, …, w_{G}\}</tex> - множество выходных сигналов или выходной алфавит АА.
4. δ - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие состояние АА <tex>a_{s}</tex>, т.е. <tex>a_{s} = δ(a_{m}, z_{f})</tex>, <tex>a_{s}∈A</tex>.
5. λ - функция выходов АА, которая некоторым парам \<состояние – входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие выходной сигнал АА <tex>w_{g}</tex>, т.е. <tex>w_{g}=λ(a_{m},z_{f})</tex>, <tex>w_{g}∈W</tex>.
6. <tex>а_{1}</tex> - начальное состояние АА.
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
2. Сумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
называется '''кодом Хаффмана'''.
}}
