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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

17
Рис.1.1. Граф недетерминированного автомата Мура
Поставив в соответствие каждой вершине графа событие перехода в
эту вершину, получим следующую отмеченную недетерминированную СКУ
не полностью определенного НДА Муpa:
)()(&)()1(
0
1
0
0
0
t
x
txt
S
t
S
y
;
)()()(&)()1(
110
1
1
txt
S
t
x
t
S
t
S
y
;
)()(&)()(&)()1(
2
1
110
2
2
t
x
txt
S
t
x
t
S
t
S
y
; (1.8)
);(&)(
)(&)()(&)()(&)()1(
454
3
31221
3
43
t
x
t
SS
txt
S
t
x
t
S
t
x
t
S
tS
yy
);(&)(
)(&)(&)()(&)()1(
4
54
323
1
2
4
42
txt
SS
t
x
t
x
t
S
txt
S
t
S
yy
)(&)(&)()1(
12
5
31
txt
x
t
S
t
S
yy
.
Примечание: В дальнейшем, если позволяет контекст, знаки & и время t в правой
части СКУ для простоты будем опускать.
По НД СКУ автомата Мура в соответствии с (1.6) получим СВФ не
полностью определенного НДА Мура (1.9):
S
y
0
0
SS
y
51
1
SS
y
42
2
SS
y
53
3
SS
y
43
4
(1.9)
НД СКУ автомата Мили, эквивалентного автомату Мура, получим из
(1.8) путем объединения тех событий НД СКУ автомата Мура, переходы из
которых полностью совпадают. К таким событиям относятся события S
4
и S
5
,
переходы из которых совпадают:
SxSS
3454
)
(
,
SxSS
4454
)(
. При
этом для всех букв левой части уравнений для НД СКУ автомата Мили
опускаются отмечающие их выходные сигналы. Делая замену переменных
SSS
454
и их подстановку в (1.8), получим НД СКУ не полностью
определенного автомата Мили:
x
x
S
t
S
0
1
00
)1(
;
2
1101
)1( x
SxS
t
S
;
x
x
SxS
t
S
2
1
1102
)1(
; (1.10)
xS
x
SxSxS
t
S
44
3
312213
)1(
;
4
4323
21
24
)1( x
SxxS
xx
S
t
S
.
По НД СКУ автомата Мура в соответствии с (1.7) и учитывая замену
SSS
454
, получим СВФ не полностью определенного НДА Мили: 
               Рис.1.1. Граф недетерминированного автомата Мура


      Поставив в соответствие каждой вершине графа событие перехода в
эту вершину, получим следующую отмеченную недетерминированную СКУ
не полностью определенного НДА Муpa:
          y
        S 0 0 (t  1)  S 0 (t ) & x1 (t )  x0 (t ) ;
           y
        S 1 1 ( t  1)  S 0 ( t ) & x1 ( t )  S 1 ( t ) x ( t ) ;
          y
        S 22 (t  1)  S 0 (t ) & x1 (t )  S1 (t ) & x1 (t ) x2 (t ) ;                    (1.8)
        S 3y3 y4 (t  1)  S1 (t ) & x2 (t )  S 2 (t ) & x1 (t )  S 3 (t ) & x3 (t ) 
         S 4  S 5 (t ) & x4 (t );
        S 4y2 y4 (t  1)  S 2 (t ) & x1 (t )  S 3 (t ) & x2 (t ) & x3 (t ) 
         S 4  S 5 (t ) & x4 (t );
          y y
        S 5 1 3 ( t  1)  S 2 ( t ) & x1 ( t ) & x ( t ) .

       Примечание: В дальнейшем, если позволяет контекст, знаки & и время t в правой
части СКУ для простоты будем опускать.
     По НД СКУ автомата Мура в соответствии с (1.6) получим СВФ не
полностью определенного НДА Мура (1.9):

     y0  S 0                     y1  S 1  S 5            y2  S 2  S 4
     y3  S 3  S 5               y4  S 3  S 4                                           (1.9)

       НД СКУ автомата Мили, эквивалентного автомату Мура, получим из
(1.8) путем объединения тех событий НД СКУ автомата Мура, переходы из
которых полностью совпадают. К таким событиям относятся события S4 и S5,
переходы из которых совпадают: (S 4  S 5) x 4  S 3 , (S 4  S 5) x 4  S 4 . При
этом для всех букв левой части уравнений для НД СКУ автомата Мили
опускаются отмечающие их выходные сигналы. Делая замену переменных
S 4  S 5  S 4 и их подстановку в (1.8), получим НД СКУ не полностью
определенного автомата Мили:
                S 0 (t  1)  S 0 x1  x0 ;
                S 1 (t  1)  S 0 x1  S 1 x2 ;
                S 2 (t  1)  S 0 x1  S1 x1 x2 ;                     (1.10)
                S 3 (t  1)  S1 x 2  S 2 x1  S 3 x3  S 4 x 4 ;
                S 4 (t  1)  S 2  x1  x2   S 3 x 2 x3  S 4 x4 .

       По НД СКУ автомата Мура в соответствии с (1.7) и учитывая замену
S 4  S 5  S 4 , получим СВФ не полностью определенного НДА Мили:

                                                                                                   17

Страницы