Противогоночное кодирование автоматов

Страницы работы

23 страницы (Word-файл)

Содержание работы

Домашка № 19.

Противогоночное кодирование автоматов.

Таблица переходов:

0q0

Qq1

2q2

2q3

4q4

5q5

6q6

7q7

8q8

9q9

XX0

Qq0

2q2

2q2

4q4

4q4

0q0

6q6

8q8

8q8

9q0

XX1

0q0

1q1

3q3

3q3

0q0

0q0

7q7

7q7

9q9

9q9

XX2

6q6

2q2

2q2

4q4

4q4

5q5

6q6

8q8

8q8

5q5

XX3

1q1

1q1

3q3

4q3

5q5

5q5

7q7

7q7

9q9

9q9

Таблица выходов:

0q0

Qq1

2q2

2q3

4q4

5q5

6q6

7q7

8q8

9q9

XX0

Yy0

Yy0

Yy0

1y1

Yy1

Yy0

Yy0

Yy1

Yy1

Yy1

XX1

Yy0

Yy0

Yy1

Yy1

Yy0

Yy0

Yy0

Yy0

Yy1

Yy1

XX2

Yy0

Yy0

0y0

Yy1

Yy1

Yy0

Yy0

Yy1

Yy1

Yy1

XX3

Yy0

Yy0

Yy1

Yy1

Yy0

Yy0

Yy0

Y0

Yy1

Yy1

X1X2Граф автомата:

  ,q4,q3,q1,q2,q7,q6,q5,q0,q8,q9,X3,y0,X0,X1,y0,y0,X2,y0,X0,X1,y0,y0,y0,y0,y0,y0,y0,y0,y0,y0,y0,y0,y1,y1,y1,y1,y1,y1,y1,y1,X1,X3,X1,X3,X0,X2,X0,X2,X0,y1,y1,X2,X3,X0,X2,X1,X3,X0,X2,X1,X3,y0,X3,y0,X0,X2,y0,y0,X1,X3,y1,y1,X0,X2,y1,y1,X1,X3,y0,y0,X0,X2,y1,y1,X1,X3,y1,y1
 


В графе есть контуры нечётной длины, и мы не можем провести противогоночное кодирование , не изменяя таблицу переходов. Кроме того, у состояния q0 есть пять соседних состояний, значит для кодирования состояний автомата соседним кодом нужно не менее пяти разрядов. Для кодирования же десяти состояний нужно четыре разряда. Поэтому мы выберем противогоночное кодирование с устранением только критических состязаний.

Переходы:

 (по )

 (по )

 (по )

 (по )

(q0,q0)

(q0,q0)

(q0,q6)

(q0,q1)

(q1,q2)

(q1,q1)

(q1,q2)

(q1,q1)

(q2,q2)

(q2,q3)

(q2,q2)

(q2,q3)

(q3,q4)

(q3,q3)

(q3,q4)

(q3,q3)

(q4,q4)

(q4,q0)

(q4,q4)

(q4,q5)

(q5,q0)

(q5,q0)

(q5,q5)

(q5,q5)

(q6,q6)

(q6,q7)

(q6,q6)

(q6,q7)

(q7,q8)

(q7,q7)

(q7,q8)

(q7,q7)

(q8,q8)

(q8,q9)

(q8,q8)

(q8,q9)

(q9,q0)

(q9,q9)

(q9,q5)

(q9,q9)

Теперь будем обозначать q0 как 0, q1 как1 и т.д.

Таблица пар состояний, подлежащих развязыванию:

 (по )

 (по )

 (по )

 (по )

1

(00),(12)

(00),(11)

(06),(12)

(01),(23)

2

(00),(22)

(00),(23)

(06),(22)

(01),(33)

3

(00),(34)

(00),(33)

(06),(34)

(01),(45)

4

(00),(44)

(00),(67)

(06),(44)

(01),(55)

5

(00),(66)

(00),(77)

(06),(55)

(01),(67)

6

(00),(78)

(00),(89)

(06),(78)

(01),(77)

7

(00),(88)

(00),(99)

(06),(88)

(01),(89)

8

(12),(34)

(11),(23)

(06),(95)

(01),(99)

9

(12),(44)

(11),(33)

(12),(34)

(11),(23)

10

(12),(50)

(11),(40)

(12),(44)

(11),(33)

11

(12),(66)

(11),(50)

(12),(55)

(11),(45)

12

(12),(78)

(11),(67)

(12),(66)

(11),(55)

13

(12),(88)

(11),(77)

(12),(78)

(11),(67)

14

(12),(90)

(11),(89)

(12),(88)

(11),(77)

15

(22),(34)

(11),(99)

(12),(95)

(11),(89)

 (по )

 (по )

 (по )

 (по )

16

(22),(44)

(23),(40)

(22),(34)

(11),(99)

17

(22),(50)

(23),(50)

(22),(44)

(23),(45)

18

(22),(66)

(23),(67)

(22),(55)

(23),(55)

19

(22),(78)

(23),(77)

(22),(66)

(23),(67)

20

(22),(88)

(23),(89)

(22),(78)

(23),(77)

21

(22),(90)

(23),(99)

(22),(78)

(23),(89)

22

(34),(50)

(33),(40)

(22),(95)

(23),(99)

23

(34),(66)

(33),(50)

(34),(55)

(33),(45)

24

(34),(78)

(33),(67)

(34),(66)

(33),(55)

25

(34),(88)

(33),(77)

(34),(78)

(33),(67)

26

(34),(90)

(33),(89)

(34),(88)

(33),(77)

27

(44),(50)

(33),(99)

(34),(95)

(33),(89)

28

(44),(66)

(40),(67)

(44),(55)

(33),(99)

29

(44),(78)

(40),(77)

(44),(66)

(45),(67)

30

(44),(88)

(40),(89)

(44),(78)

(45),(77)

31

(44),(90)

(40),(99)

(44),(88)

(45),(89)

32

(50),(66)

(50),(67)

(44),(95)

(45),(99)

33

(50),(78)

(50),(77)

(55),(66)

(55),(67)

 (по )

 (по )

 (по )

 (по )

34

(50),(88)

(50),(89)

(55),(78)

(55),(77)

35

(66),(78)

(50),(99)

(55),(88)

(55),(89)

36

(66),(88)

(67),(89)

(66),(78)

(55),(99)

37

(66),(90)

(67),(99)

(66),(88)

(67),(89)

38

(78),(90)

(77),(89)

(66),(95)

(67),(99)

39

(88),(90)

(77),(99)

(78),(95)

(77),(89)

40

(88),(95)

(77),(99)

Похожие материалы

Информация о работе