Специальная математика. Соловьев А.Е. - 46 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

x
1
Переход от автомата Мили к автомату Мура.
Т.П. q
1
/b
0
q
2
q
3
x
1
q
1
/b
11
q
3
/b
21
q
2
/b
31
x
2
q
2
/b
12
q
1
/b
22
q
3
/b
32
Т.В. q
1
q
2
q
3
x
1
y
3
y
1
y
2
x
2
y
4
y
5
y
6
y
3
y
4
y
1
y
5
y
2
y
6
b
0
b
11
b
12
b
21
b
22
b
31
b
32
x
1
b
11
b
11
b
21
b
31
b
11
b
21
b
31
x
2
b
12
b
12
b
22
b
32
b
12
b
22
b
32
Теорема : (Глушкова)
Таким образом доказана конструктивная теорема, что для произвольного автомата Милли
может быть построен эквивалентный ему автомат Мура имеющий не более
n * m + 1 состояний, где n - число входных сигналов, m - число состояний исходного
автомата Милли.
4.Теория графов
4.1. Понятие графа
Начало теории графов часто ведут от 1736 года и связывают с решением Эйлером
знаменитой задачи о Кенигсбергских мостах.
С C
A D A D
В B
Жителям в те далекие времена, чтобы придать воскресному гулянию осмысленность,
предлагалось выйдя из дома (на любом участке суши (А, В, С или D) пройти по всем мостам
строго по одному разу и вернуться домой….
На втором рисунке этот корявый план нарисован в виде графа.
— 46 —
q
i
x
j
y
ij
Переход от автомата Мили к автомату Мура. x1

Т.П.
qixj  q1/b0            q2         q3
yxij  q /b             q3/b21     q2/b31
  1     1 11
 x2    q2/b12           q1/b22     q3/b32

Т.В.         q1         q2         q3
x1           y3         y1         y2
x2           y4         y5         y6

                  y3        y4    y1        y5    y2    y6
       b0         b11       b12   b21       b22   b31   b32
x1     b11        b11       b21   b31       b11   b21   b31
x2     b12        b12       b22   b32       b12   b22   b32

Теорема : (Глушкова)
Таким образом доказана конструктивная теорема, что для произвольного автомата Милли
может быть построен эквивалентный ему автомат Мура имеющий не более
n * m + 1 состояний, где n - число входных сигналов, m - число состояний исходного
автомата Милли.
                                                  4.Теория графов

                                                  4.1. Понятие графа

Начало теории графов часто ведут от 1736 года и связывают с решением Эйлером
знаменитой задачи о Кенигсбергских мостах.




                              С                                        C




     A                                  D                              A   D


                        В                                              B

Жителям в те далекие времена, чтобы придать воскресному гулянию осмысленность,
предлагалось выйдя из дома (на любом участке суши (А, В, С или D) пройти по всем мостам
строго по одному разу и вернуться домой….
На втором рисунке этот корявый план нарисован в виде графа.


                                                         — 46 —

Страницы