Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 16 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

16
элементарный выходной сигнал, т.е. для автомата Мили СВФ будет иметь
вид
Nkt
S
t
y
j
kjj
Y
j
yYS
k
,1),1()(
V
, (1.7)
где в правую часть выражения (1.7) необходимо сделать подстановку из (1.1).
Сравнивая выражения (1.5) и (1.7), подтверждаем тот факт, что
выходной сигнал автомата Мура отстает на один такт по сравнению с
выходным сигналом эквивалентного ему автомата Мили. Кроме того, следует
иметь в виду, что выходные сигналы автомата Мура отличаются от
выходных сигналов эквивалентного ему автомата Мили по времени
действия, а именно: выходной сигнал автомата Мура действует от момента
появления события и до его исчезновения, а выходной сигнал автомата Мили
действует от момента появления входного сигнала и до его исчезновения.
Система функций переходов для автомата Мили, эквивалентного ему
автомата Мура, может быть получена из системы уравнений (1.1) путем
объединения тех событий НД СКУ автомата Мура, переходы из которых
полностью совпадают.
П р и м е р 1.1. Пусть НДА Мура задан графом (рис.1.1), в котором в
качестве входного и выходного алфавитов используются структурные
алфавиты:
Х = x
0
, x
1
, x
2
, x
3
, x
4
, Y = y
0
, y
1
, y
2
, y
3
, y
4
,
где x
0
- сигнал приведения автомата в исходное состояние.
Построить для этого графа НД СКУ и СВФ для моделей автомата Мура
и Мили.
Как видно из рисунка, представленный графом НДА Мура является
также и не полностью определенным, так как из вершины 3 не
удовлетворяются условия полноты переходов.
0
x
1
1
2
3
5
4
y
0
x
1
y
1
x
2
x
2
x
3
y
3
y
4
x
2
x
3
x
4
x
4
y
2
y
4
x
4
x
1
x
1
x
0
y
2
x
1
x
1
x
2
y
3
y
4
x
4
x
1
x
2
элементарный выходной сигнал, т.е. для автомата Мили СВФ будет иметь
вид
                                              Y
                    y k (t )        V
                                 S Y  y 
                                             S j (t  1), k  1, N ,
                                                    j                                       (1.7)
                                   j    j     k

где в правую часть выражения (1.7) необходимо сделать подстановку из (1.1).
      Сравнивая выражения (1.5) и (1.7), подтверждаем тот факт, что
выходной сигнал автомата Мура отстает на один такт по сравнению с
выходным сигналом эквивалентного ему автомата Мили. Кроме того, следует
иметь в виду, что выходные сигналы автомата Мура отличаются от
выходных сигналов эквивалентного ему автомата Мили по времени
действия, а именно: выходной сигнал автомата Мура действует от момента
появления события и до его исчезновения, а выходной сигнал автомата Мили
действует от момента появления входного сигнала и до его исчезновения.
      Система функций переходов для автомата Мили, эквивалентного ему
автомата Мура, может быть получена из системы уравнений (1.1) путем
объединения тех событий НД СКУ автомата Мура, переходы из которых
полностью совпадают.
      П р и м е р 1.1. Пусть НДА Мура задан графом (рис.1.1), в котором в
качестве входного и выходного алфавитов используются структурные
алфавиты:
                 Х =  x0, x1, x2, x3, x4, Y = y0, y1, y2, y3, y4,
где x0 - сигнал приведения автомата в исходное состояние.
     Построить для этого графа НД СКУ и СВФ для моделей автомата Мура
и Мили.
     Как видно из рисунка, представленный графом НДА Мура является
также и не полностью определенным, так как из вершины 3 не
удовлетворяются условия полноты переходов.

                                   x2                           x3


                                                   x2                                 x4
                          y1       1                            3         y3y4
        y0     x1
                                                                               x2x3
                                                  x1
x1      0                              x1x2                          x4                     4       x4
                    x1                                     x1             x4               y2y4
 x0
                         y2        2                            5         y3y4
                                                  x 1x 2




                                                                                                         16

Страницы