- •Понятие множества. Способы задания множеств.
- •Операции над множествами. Диаграммы Эйлера-Венна.
- •Алгебра множеств.
- •Кортеж. График. Свойства графиков.
- •Соответствия. Свойства соответствий.
- •Отношения. Свойства отношений. Примеры.
- •Высказывания. Операции над высказываниями.
- •Формы представления высказываний. Примеры.
- •Преобразования высказываний. Примеры.
- •Минимизация высказываний методом Квайна. Пример.
- •Минимизация высказываний с помощью карт Карно. Пример.
- •Понятие графа. Способы задания графа. Пример.
- •Виды графов: эйлеров, полный, планарный, деревья. Примеры.
- •Определение путей в графе. Пример.
- •Приведение графа к ярусно-параллельной форме. Пример.
- •Внутренняя и внешняя устойчивость графа. Ядро графа. Пример.
- •4.9. Множество внешней устойчивости. Ядро графа
- •Поиск минимального остова в графе.
- •Понятие автомата. Виды автоматов.
- •Минимизация автоматов.
- •Переход от автомата Милли к автомату Мура и наоборот.
-
Переход от автомата Милли к автомату Мура и наоборот.
Автоматы Мура и Мили отличаются функцией выходов.
y(t) = (q(t)) – для автомата Мура
и
y(t) = (q(t-1), x(t)) – для автомата Мили
Переход от автомата Мура к автомату Мили заключается в построении таблицы переходов. Построение состоит в подстановке выходных сигналов, отмечающих состояния в расширенной таблице переходов, вместо состояний, в которые автомат переходит. Тем самым, если говорить в терминах графов, выходные сигналы от состояний сдвигаются на стрелки, которые в эти состояния заходят.
А таблица переходов автомата Мили получается из расширенной таблицы переходов автомата Мура отбрасыванием первой строки.
х1
|
y1 |
y3 |
y2 |
A x2 |
A |
B |
C |
x1 |
A |
B |
A |
x1 x1 B x3 |
B |
B |
C |
x3 |
C |
A |
C |
y2 y3 x2
x2 x3
y1
Т.П. |
A |
B |
C |
x1 |
A |
B |
A |
x2 |
B |
B |
C |
x3 |
C |
A |
C |
Т.В. |
A |
B |
C |
x1 |
y1 |
y3 |
y1 |
x2 |
y3 |
y3 |
y2 |
x3 |
y2 |
y1 |
y2 |
П
x1
qixj
yij
bij |
q1/b0 |
q2 |
q3 |
x1 |
q1/b11 |
q3/b21 |
q2/b31 |
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 - число состояний исходного автомата Милли.