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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

40
.)()1(
;)1(
;)()1(
;
)()1(
;)()1(
);())((
))((
)()1(
)2.2(;)()1(
;)()(
)()1(
;)1(
;)
)(()1(
;)()1(
;)1(
;)1(
43
2432
124
12
32
184
32
13
11
3
2
18
42
13
2
13
10
4
93
1
8
4
31110735
4
3
1
3
9
3
2
1
64
3
2
1
12442
1
2
8
321
31
843
43
11107
3216321
4
21124
4
213214
131
3
4
212
7
32
64
32
1244
2
2
6
494
3
11107
3
2186
3
5
4
3
2131244212211
5
2
11
4
32
1
632
1
4
2
1
124
4
2
1
22
1
1
3
3
2
6
4
3
2
124
42
2
21
1
2
10
1
0
1
0
0
43
1
2
4
1
3
43
1
2
42
432
432
4
1
3
43
431
432
421
21
0
xx
xxxx
aa
t
a
yy
y
y
xx
xax
xx
xa
t
a
y
y
y
x
x
xa
xx
xx
x
xa
t
a
yy
y
y
x
ax
x
a
x
xaaaxa
x
x
x
a
t
a
yy
x
x
x
ax
x
x
x
aaxx
x
a
t
a
yyy
xxx
xx
axx
xx
aaa
xxxaxxx
x
xxaa
x
xxxxxx
xxx
a
x
xxa
t
a
yyy
xx
ax
xx
aax
x
a
t
a
y
y
y
xax
x
aaa
x
xxaa
x
a
x
x
xxaaaxxxaxxa
t
a
yy
x
xa
t
a
yyy
xx
x
axx
x
x
x
x
aa
x
x
x
ax
x
a
t
a
yyy
x
x
a
x
x
x
aa
xx
a
xx
a
t
a
yyy
xa
t
a
yy
x
x
a
t
a
y
д) Система канонических уравнений детерминированного полностью
определенного автомата Мили, эквивалентного автомату Мура, может быть
получена из отмеченной СКУ (2.2) путем объединения тех состояний (табл.
2.2), для которых все переходы полностью совпадают. Для нашего примера
это соответствует двум группам состояний: (a
4
,a
12
) и (a
7
,a
10
,a
11
). Делая
необходимые замены и подстановки переменных вида: a
4
a
12
=a
4
и
(a
7
a
10
a
11
)=a
7
в (2.2), получим следующую СКУ автомата Мили: 
     a 0y 0 (t  1)  a0 x1  x0 ;
     a1y1 y 2 (t  1)  a0 x1;
     a 2y1 y 2 y 4 (t  1)  a1 x1 x2  a2 x2 x4  (a 4  a12) x2 x3 x4  a6 x2 x3 ;
     a y 2 y 3 y 4 (t  1)  a1 x x2  a 2 x x2 x  (a 4  a12)( x x2 x 
      3                         1           1     4                    1       4

      x1 x2 x3)  a6 x1 x2 x3 ;
     a 4y1 y3 y 4 (t  1)  a1 x1 x2 ;
     a5y 3 y 4 (t  1)  a1 x1 x2  a 2 x1 x2 x4  (a 4  a12  a3) x1 x2 x3 x4 
      a5 x3  (a6  a8) x1 x 2 x3  (a7  a10  a11) x3 x4  a9 x4 ;
     a 6y1 y 3 y 4 (t  1)  a 2 x2 x4  (a 4  a12) x2 x3 x4  a6 x2 x3 ;                  (2.2)
     a 7y 2 y 3 y 4 (t  1)  a2 x1 x2 x4  a3 ( x1 x3  x1 x4  x1 x 2 x3  x1 x2 x4 ) 
     (a4  a12)( x1 x2 x4  x1 x 2 x3)  a6 x1 x2 x3 
      (a7  a10  a11)( x3 x4  x3 x4)  a8 ( x1 x3  x1 x 2 x3);
     a8y 2 y 3 y 4 (t  1)  a2 x1 x2 x 4  (a4  a12) x1 x2 x3 x4  a 6 x1 x2 x3 ;
     a y 2 y 4 (t  1)  a3 x x3 x  a5 x3  (a7  a10  a11) x3 x 
      9                     1       4                                      4

      a8 x1 x3  a9 x4 ;
     a10y1 y 2 y 3 y 4 (t  1)  a3 ( x1 x2 x3  x1 x2 x4 )  a8 x1 x2 x3 ;
     a y1 y 3 y 4 (t  1)  a3 x1 x x x4  a8 x1 x x ;
      11                            2   3             2   3

     a12y1 y 2 y 3 y 4 (t  1)  (a 4  a12) x2 x3 x4  x2 x3 x4 .

       д) Система канонических уравнений детерминированного полностью
определенного автомата Мили, эквивалентного автомату Мура, может быть
получена из отмеченной СКУ (2.2) путем объединения тех состояний (табл.
2.2), для которых все переходы полностью совпадают. Для нашего примера
это соответствует двум группам состояний: (a4,a12) и (a7,a10,a11). Делая
необходимые замены и подстановки переменных вида: a4a12=a4 и
(a7a10a11)=a7 в (2.2), получим следующую СКУ автомата Мили:




                                                                                                    40

Страницы