Синтез Автомата с памятью

 

 

 

Кафедра электроники и сетей  ЭВМ

 

 

 

 

 

 

 

Отчет по курсовому проекту

По дисциплине «Теория автоматов»

 

 

Синтез Автомата с памятью

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Нижний Новгород

2012

 

 

1. Цель работы

Синтезировать автомат для  преобразования двоично-десятичного  кода с весами 5, 2, 2, 1, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код с весами 6, 4, 2, 1, который снимается с выхода в последовательной форме, начиная со старшего разряда. Провести синтез абстрактного автомата Мили и Мура по первой и второй стратегии. Для каждого автомата привести таблицы переходов и выходов, а также графы работы. По автомату с наименьшим числом внутренних состояний построить структурный автомат. Для структурного автомата провести минимизацию. Провести синтез комбинационной схемы автомата.

 

2. Таблицы функционирования и соответствия

                           

 

 Таблица функционирования  для синтезируемого автомата:

 

 

 

N	x1 5	x2 2	x3 2	x4 1	y1 6	y2 4	y3 2	y4 1
0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	1
2	0	0	1	0	0	0	1	0
3	0	0	1	1	0	0	1	1
4	0	1	1	0	0	1	0	0
5	0	1	1	1	0	1	0	1
6	1	0	0	1	1	0	0	0
7	1	1	0	0	1	0	0	1
8	1	0	1	1	1	0	1	0
9	1	1	1	0	1	0	1	1

 

 

 

 

 

                                                 Таблица соответствия для автомата:

 

Z доп	W *
z0 z0 z0 z0	w0 w0 w0 w0
z0 z0 z0 z1	w0 w0 w0 w1
z0 z0 z1 z0	w0 w0 w1 w0
z0 z0 z1 z1	w0 w0 w1 w1
z0 z1 z1 z0	w0 w1 w0 w0
z0 z1 z1 z1	w0 w1 w0 w1
z1 z0 z0 z1	w1 w0 w0 w0
z1 z1 z0 z0	w1 w0 w0 w1
z1 z0 z1 z1	w1 w0 w1 w0
z1 z1 z1 z0	w1 w0 w1 w1

3. Абстрактный синтез  автомата

3.1. Информативное нагруженное дерево, соответствующие ему графы и  таблицы переходов

 

Ниже представлено информативное  нагруженное дерево, соответствующее  синтезируемому автомату:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.2. Разметка вход-выходных слов

 

В данной работе были произведены  разметки вход-выходных слов для автоматов  Мили и Мура по 1-й и 2-й стратегии. Первая стратегия предполагает немедленное  введение нового состояния там, где  переход еще не определен, вторая стратегия стремится обойтись старыми  состояниями.

Разметка автомата Мили по первой стратегии

 

0 z0 z0 z0 z0   

 

      1 w0     2  w0    3 w0    4 w0      1  

 

1 z0 z0 z0 z1  

 

      1 w0     2  w0     3 w0    4 w1      1

 

2 z0 z0 z1 z0  

 

      1 w0     2  w0     3 w1    5 w0    1

 

3 z0 z0 z1 z1 

 

      1 w0     2   w0    3 w1   5  w1    1

 

4 z0 z1 z1 z0  

 

      1 w0     2  w1   6 w0     7 w0         1

 

5 z0 z1 z1 z1   

 

      1 w0     2  w1    6 w0     7 w1    1   

 

6 z1 z0 z0 z1   

 

      1 w1     8 w0     9 w0    10 w0    1    

 

7 z1 z1 z0 z0  

 

      1     w1   8  w0    11 w0 12 w1         1

 

8 z1 z0 z1 z1  

 

      1 w1     8  w0  9  w1   13 w0    1

 

9 z1 z1 z1 z0  

 

      1 w1     8  w0   11 w1   14 w1        1

 

Совмещенная таблица переходов  автомата Мили, синтезированного по таблице  соответствия:

 

a(t)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

z(t)

z0

а2

а3

а4

а1

а1

-

а1

a9

a10

-

a12

a1

-

a1

w0

w0

w0

w0

w0

-

w0

w0

w0

-

w0

w1

-

w1

z1

a8

a6

a5

а1

а1

a7

а1

a11

a13

a1

а14

-

a1

-

w1

w1

w1

w1

w1

w0

w1

w0

w1

w0

w1

-

w0

-

 

 

 

 

 

 

 

Граф автомата Мили, синтезированный по первой стратегии:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

              

 

 

 

 

 

 

 

 

Разметка автомата Мили по второй стратегии

 

0 z0 z0 z0 z0   

 

      1 w0     2  w0    3 w0    4 w0      1  

 

1 z0 z0 z0 z1  

 

      1 w0     2  w0     3 w0    4 w1      1

 

2 z0 z0 z1 z0  

 

      1 w0     2  w0     3 w1    5 w0    1

 

3 z0 z0 z1 z1 

 

      1 w0     2   w0    3 w1    5  w1    1

 

4 z0 z1 z1 z0  

 

      1 w0     2  w1    6 w0     7 w0         1

 

5 z0 z1 z1 z1   

 

      1 w0     2  w1    6 w0     7 w1    1   

 

6 z1 z0 z0 z1   

 

      1 w1     8  w0     3 w0     4 w0    1    

 

7 z1 z1 z0 z0  

 

      1     w1     8  w0    9  w0    4 w1         1

 

8 z1 z0 z1 z1  

 

      1 w1     8  w0     3  w1    5 w0    1

 

9 z1 z1 z1 z0  

 

      1 w1    8  w0     9 w1     5 w1         1

 

 

 

 

 

 

 

Совмещенная таблица переходов  и выходов для автомата Мили:

 

a(t)	a1	a2	a3	a4	a5	a6	a7	a8	a9
z(t)
z0	а2	а3	а4	а1	а1	-	а1	a3	a4
	w0	w0	w0	w0	w0	-	w0	w0	w0
z1	a7	a6	a5	а1	а1	a7	a1	a9	a5
	w1	w1	w1	w1	w1	w0	w1	w0	w1

 

 

 

 

 

 

 

Граф автомата Мили, синтезированный по второй стратегии:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Разметка автомата Мура по первой стратегии

 

 

0 z0 z0 z0 z0 c  

 

      1 w0     2   w0   3 w0    4 w0    5 c 1

 

1 z0 z0 z0 z1 c  

 

      1 w0     2   w0    3 w0    4 w1    6 c 1 

 

2 z0 z0 z1 z0 c  

 

      1 w0     2  w0     3 w1     7 w0   8 c            1

 

3 z0 z0 z1 z1 c  

 

      1 w0     2  w0     3 w1     7 w1     9 c    1

 

4 z0 z1 z1 z0 c  

 

      1 w0     2  w1   10 w0   11 w0   12 c    1

 

5 z0 z1 z1 z1 c  

 

      1     w0     2  w1   10 w0  11 w1   13 c   1

 

6 z1 z0 z0 z1 c  

 

      1 w1   14 w0   15 w0   16 w0   17 c 1

 

7 z1 z1 z0 z0 c  

 

      1 w1   14 w0   18  w0  19 w1   20 c           1

 

8 z1 z0 z1 z1 c  

 

      1 w1   14  w0   15  w1  21  w0  22 c   1

 

9 z1 z1 z1 z0 c  

 

      1 w1   14  w0   18 w1   23 w1   24 c     1

 

 

 

a(t)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

a15

a16

a17

a18

a19

a20

a21

a22

a23

a24

z(t)

z0

а2

а3

а4

а5

a1

а1

а8

a1

a1

-

a12

а1

а1

a15

а16

-

a1

а19

a20

а1

-

а1

a24

а1

w0

w0

w0

w0

c

c

w0

c

c

-

w0

c

c

w0

w0

-

c

w0

w1

с

-

с

w1

с

z1

a14

a10

a7

a6

a1

a1

a9

a1

a1

a14

a13

а1

а1

a18

a21

а17

a1

a23

-

а1

a22

а1

-

а1

w1

w1

w1

w1

c

c

w1

c

c

w0

w1

c

c

w1

w1

w0

c

w1

-

с

w0

с

-

с