Автоматы Мура и Мили — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Абстрактные автоматы)
(→‎Абстрактные автоматы)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, δ, λ, a_{1})</tex>, где
+
'''Абстрактный автомат''' (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, δ, λ, a_{1})</tex>, где
  
 
1. <tex>A=\{a_{1}, ..., a_{m}, ..., a_{M}\}</tex> - множество состояний или алфавит состояний АА.
 
1. <tex>A=\{a_{1}, ..., a_{m}, ..., a_{M}\}</tex> - множество состояний или алфавит состояний АА.
Строка 16: Строка 16:
  
 
6. <tex>а_{1}</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>)
 
−
 
−
называется '''кодом Хаффмана'''.
 
 
}}
 
}}

Версия 20:37, 7 января 2015

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

Определение:
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором [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] - начальное состояние АА.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Автоматы_Мура_и_Мили&oldid=43562»