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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

52
Таблица 3.4
Шаг
алгоритма
a
i
(t) X
i,j
(t) a
j
(t+1) Y
i,j
(t)
1 2 3 4 5
1 a
0
1 a
1
y
1
2 a
1
x
1
a
2
y
2
x
1
a
3
y
3
3 a
2
1 a
3
y
3
4 a
3
1 a
4
y
1
5 a
4
x
1
a
3
y
2
x
1
a
5
y
3
6 a
5
x
3
a
6
y
4
x
3
a
5
y
5
7 a
6
1 a
7
y
k
Минимальную СКУ для автомата Мили и соответствующую СВФ
можно получить одним из двух способов. В первом случае, если
минимальная прямая таблица переходов уже построена, то по ней не трудно
построить минимальную СКУ и СВФ. Во втором случае, если минимальная
прямая таблица переходов не строилась, а исходный автомат был задан СКУ
и СВФ, то минимальную СКУ и СВФ можно построить путем склеивания
(объединения) правых частей уравнений для одинаково обозначенных
событий и подстановки новых обозначений в исходные СКУ и СВФ. Для
нашего примера имеем:
S
0
=a
0
; S
1
=a
1
; S
2
=a
2
; S
3
S
5
=a
3
; S
4
S
8
=a
4
;
S
6
S
7
S
10
=a
5
; S
9
=a
6
; S
k
=a
7
.
Откуда получим минимальные СКУ и СВФ автомата Мили:
.)1(
.;)1(
;;)1(
;;)1(
;;)1(
;)(;)1(
;;)1(
67
6356
35
5
35145
35
4
34
14211
3
141123
141
2
112
30
1
01
a
t
a
a
y
xa
t
a
xa
y
xaxa
t
a
xa
y
a
t
a
xaaxa
y
xaxaa
t
a
xaa
y
xa
t
a
aa
y
a
t
a
k
Цифровой автомат Мура. Минимальная таблица переходов автомата
Мура для нашего примера с учетом эквивалентности двух пар событий и
введенных обозначений для классов эквивалентного разбиения: 
                                                                       Таблица 3.4
      Шаг                    ai(t)        Xi,j(t)           aj(t+1)   Yi,j(t)
   алгоритма
       1                      2             3                    4     5
       1                      a0            1                    a1    y1
       2                      a1            x1                   a2    y2
                                            x1                   a3    y3
       3                      a2            1                    a3    y3
       4                      a3            1                    a4    y1
       5                      a4            x1                   a3    y2
                                            x1                   a5    y3
       6                      a5            x3                   a6    y4
                                            x3                   a5    y5
       7                      a6            1                    a7    yk

      Минимальную СКУ для автомата Мили и соответствующую СВФ
можно получить одним из двух способов. В первом случае, если
минимальная прямая таблица переходов уже построена, то по ней не трудно
построить минимальную СКУ и СВФ. Во втором случае, если минимальная
прямая таблица переходов не строилась, а исходный автомат был задан СКУ
и СВФ, то минимальную СКУ и СВФ можно построить путем склеивания
(объединения) правых частей уравнений для одинаково обозначенных
событий и подстановки новых обозначений в исходные СКУ и СВФ. Для
нашего примера имеем:
      S0=a0;         S1=a1;        S2=a2;        S3S5=a3; S4S8=a4;
      S6S7S10=a5;         S9=a6;        Sk=a7.
      Откуда получим минимальные СКУ и СВФ автомата Мили:
      a1 (t  1)  a0 ;                    y1  a0  a3 ;
     a2 (t  1)  a1 x1;                   y 2  (a1  a4) x1;
     a3 (t  1)  a 2  a1 x1  a 4 x1;    y3  a1 x1  a2  a4 x1;
     a 4 (t  1)  a3 ;                    y 4  a 5 x3 ;
     a5 (t  1)  a 4 x1  a5 x 3 ;        y5  a5 x 3 ;
     a 6 (t  1)  a5 x3 ;                 yk  a6 .
     a 7 (t  1)  a6 .
     Цифровой автомат Мура. Минимальная таблица переходов автомата
Мура для нашего примера с учетом эквивалентности двух пар событий и
введенных обозначений для классов эквивалентного разбиения:



                                                                                52

Страницы