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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Способы задания автоматов)
(Абстрактные автоматы)
Строка 26: Строка 26:
 
|- style="background: white; border: 0px solid white" |
 
|- style="background: white; border: 0px solid white" |
 
| style="padding: 10px 70px 10px 20px" |
 
| style="padding: 10px 70px 10px 20px" |
<div style="font-size: 16px; font-weight:bold">Автомат Мура</div>
+
<div style="font-size: 16px; font-weight:bold">Автомат Мили</div>
 
<tex>a(t+1) = \delta (a(t), z(t))</tex>
 
<tex>a(t+1) = \delta (a(t), z(t))</tex>
  
<tex>w(t) = \lambda (a(t))</tex>
+
<tex>w(t) = \lambda (a(t), z(t))</tex>
 
||
 
||
<div style="font-size: 16px; font-weight:bold">Автомат Мили</div>
+
<div style="font-size: 16px; font-weight:bold">Автомат Мура</div>
 
 
 
<tex>a(t+1) = \delta (a(t), z(t))</tex>
 
<tex>a(t+1) = \delta (a(t), z(t))</tex>
  
<tex>w(t) = \lambda (a(t), z(t))</tex>
+
<tex>w(t) = \lambda (a(t))</tex>
 
|}
 
|}
  

Версия 22:36, 7 января 2015

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

Определение:
Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором [math]S=(A, Z, W, \delta, \lambda, 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]\delta[/math] - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> ([math]a_{m}[/math], [math]z_{f}[/math]) ставит в соответствие состояние АА [math]a_{s}[/math], т.е. [math]a_{s} = δ(a_{m}, z_{f})[/math], [math]a_{s}\in A[/math].

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

6. [math]a_{1}[/math] - начальное состояние. АА работает в дискретные моменты времени, и в момент времени [math]t=0[/math] автомат всегда находится в состоянии [math]a_{1}[/math].


Выходные сигналы АА зависят от того, что поступало на его вход раньше.

В каждый момент времени АА, будучи в состоянии [math]a_{m}^{t}[/math], способен воспринимать одну из букв входного алфавита [math]z_{f}^{t}[/math]. В соответствии с функцией [math]\delta[/math], АА перейдет в состояние [math]a_{1}^{t+1}[/math] с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов [math]\lambda[/math].

Рассмотрим функционирование автоматов Мура и Мили.

Автомат Мили

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t), z(t))[/math]

Автомат Мура

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t))[/math]

В автоматах Мура выходной сигнал определяется только состоянием автомата в какой-то момент времени и не зависит от входного сигнала в этот же момент времени.

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

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

Табличный способ задания автомата Мура

[math]\lambda[/math] [math]w_{1}[/math] [math]w_{2}[/math] [math]w_{1}[/math] [math]w_{2}[/math] [math]w_{2}[/math]
[math]\delta[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math] [math]a_{4}[/math] [math]a_{5}[/math]
[math]z_{1}[/math] [math]a_{2}[/math] [math]a_{2}[/math] [math]a_{5}[/math] [math]a_{5}[/math] [math]a_{2}[/math]
[math]z_{2}[/math] [math]a_{3}[/math] [math]a_{3}[/math] [math]a_{1}[/math] [math]a_{1}[/math] [math]a_{4}[/math]