Теория автоматов. - 5 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

автомата Мура (табл. 4). Попав в любое из таких состояний, автомат Мура дол-
жен обеспечить дальнейшую реализацию прежней функции переходовтолько
уже в ”терминах” состояний автомата Мура, т.е. состояния b
0,
b
03,
b
12,
b
13,
b
21,
b
22,
и b
23
должны обеспечить переходы, аналогичные тем, которые имели место для
состояния q
0
в автомате Мили,
b
01
-аналогичное q
1
, а b
02
и
b
11
-аналогичные
q
2
.
Полученный автомат Мура приведен в табл. 5.
Пусть не смущает, что автомат получился явно избыточным, уменьшить
число состояний- дело техники. Главное, что он ”работает” точно так же, как и
исходный автомат Мили.
Таблица 4
Таблица 5
Таким образом, существует стандартный прием, с помощью котороко
можно преобразовать автомат Мили в эквивалентных ему автомат Мура. При-
чем, если в автомате Мили n внутренних состояний и m входных то в получен-
ном автомате Мура будет n
∗
m+1 состояний.
Переход от автомата Мура
К эквивалентному автомату Мили
Из анализа переходов автоматов Мили и Мура следует, что для перехода
от автомата Мили к автомату Мура необходимо как бы отнести каждый выход-
ной сигнал к предшествующему состоянию и входному сигналу, который пере-
вел автомат Мура в данное состояние. Другими словами, на графе автомата вы-
ходные сигналы, ранее приписанные вершинам, необходимо отнести ко всем
заходящим в эту вершину дугам. Например, для автомата рис. 2 эквивалентный
автомат Мили будет иметь вид, показанный на рис.3.
Рис. 3
Н Н Б Н Б В Б В В
b
0
b
01
b
02
b
03
b
11
b
12
b
13
b
21
b
22
b
23
1 b
01
b
11
b
21
b
01
b
21
b
01
b
01
b
01
b
01
b
01
2 b
02
b
12
b
22
b
02
b
22
b
02
b
02
b
02
b
02
b
02
3 b
03
b
13
b
23
b
03
b
23
b
03
b
03
b
03
b
03
b
03
q
0
b
0
q
1
q
2
1
q
1
b
01
q
2
b
11
q
0
b
21
2
q
2
b
02
q
2
b
12
q
0
b
22
3
q
3
b
03
q
0
b
13
q
0
b
23 
автомата Мура (табл. 4). Попав в любое из таких состояний, автомат Мура дол-
жен обеспечить дальнейшую реализацию прежней функции переходовтолько
уже в ”терминах” состояний автомата Мура, т.е. состояния b0, b03, b12, b13, b21, b22,
и b23 должны обеспечить переходы, аналогичные тем, которые имели место для
состояния q0 в автомате Мили, b01 -аналогичное q1, а b02 и b11-аналогичные q2.
Полученный автомат Мура приведен в табл. 5.
       Пусть не смущает, что автомат получился явно избыточным, уменьшить
число состояний- дело техники. Главное, что он ”работает” точно так же, как и
исходный автомат Мили.
                                  Таблица 4
                                q0
                                        q1     q2
                                   b0
                                q1     q2     q0
                           1
                                   b01    b11    b21
                                q2     q2     q0
                           2
                                   b02    b12    b22
                                q3     q0     q0
                           3
                                   b03    b13    b23
                                      Таблица 5
                        Н     Н      Б    Н      Б     В     Б     В     В
                  b0    b01   b02   b03   b11   b12   b13   b21   b22   b23
             1    b01   b11   b21   b01   b21   b01   b01   b01   b01   b01
             2    b02   b12   b22   b02   b22   b02   b02   b02   b02   b02
             3    b03   b13   b23   b03   b23   b03   b03   b03   b03   b03


       Таким образом, существует стандартный прием, с помощью котороко
можно преобразовать автомат Мили в эквивалентных ему автомат Мура. При-
чем, если в автомате Мили n внутренних состояний и m входных то в получен-
ном автомате Мура будет n∗ m+1 состояний.


                            Переход от автомата Мура
                        К эквивалентному автомату Мили

       Из анализа переходов автоматов Мили и Мура следует, что для перехода
от автомата Мили к автомату Мура необходимо как бы отнести каждый выход-
ной сигнал к предшествующему состоянию и входному сигналу, который пере-
вел автомат Мура в данное состояние. Другими словами, на графе автомата вы-
ходные сигналы, ранее приписанные вершинам, необходимо отнести ко всем
заходящим в эту вершину дугам. Например, для автомата рис. 2 эквивалентный
автомат Мили будет иметь вид, показанный на рис.3.
                                                       Рис. 3

Страницы