502_KHramova_T._V._Diskretnaja_matematika_proektirovanie_konechnykh_avtomatov_v_primerakh_i_zadachakh_
.pdf
Пример 11. y(t) x1(t) x2(1).
Решение. Входной алфавит автомата {00;01;10;11} так как на входе двухэлементные последовательности x1(t)x2(t). Выходной алфавит автомата {0;1}. Выходное значение определяется символом, введенным на первом такте, причем, только второй буквой, и первой буквой символа текущего такта. На первом такте необходимо «запомнить» вторую букву входного слова, так как вариантов только два, то нам потребуется только два состояния, не считая начального. Уточним формулы для вычисления выходного значения в каждом состоянии:
S1 «x2(1) 0»: y(t) x1(t) 0 x1(t); |
S2 «x2(1) 1»: y(t) x1(t) 1 1. |
Построим диаграмму Мура (рисунок 12). |
|
Рисунок 12.
Следуя диаграмме Мура, составим таблицу переходов-выходов:
|
x(t) |
00 |
01 |
10 |
11 |
S |
|
||||
|
S0 |
S1 |
S2 |
S1 |
S2 |
|
0 |
1 |
1 |
1 |
|
|
|
||||
|
S1 |
S1 |
S1 |
S1 |
S1 |
|
0 |
0 |
1 |
1 |
|
|
|
||||
|
S2 |
S2 |
S2 |
S2 |
S2 |
|
1 |
1 |
1 |
1 |
|
|
|
||||
|
|
|
31 |
|
|
Поставим в соответствие состояниям последовательность «0» и «1»:
|
|
S |
S1S2 |
00, |
S S1S2 |
01, |
S |
2 |
S1S2 |
10 |
|
||||||||||||
|
|
0 |
|
|
0 |
0 |
|
|
1 |
|
|
1 |
1 |
|
|
|
|
2 |
2 |
|
|
|
|
Составим каноническую таблицу |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
1 |
|
2 |
|
|
x (t) |
|
x |
2 |
(t) |
|
y(t) |
|
|
|
1 |
|
|
|
2 |
|
||
|
Si |
(t) |
|
Si |
(t) |
|
1 |
|
|
|
|
|
|
|
|
Si |
(t 1) |
|
Si |
(t 1) |
|||
|
|
0 |
|
|
0 |
|
|
0 |
|
|
0 |
|
0 |
|
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
0 |
|
|
0 |
|
|
1 |
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
1 |
|
|
0 |
|
1 |
|
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
0 |
|
|
1 |
|
|
1 |
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
|
0 |
|
0 |
|
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
|
1 |
|
0 |
|
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
1 |
|
|
0 |
|
1 |
|
|
|
|
0 |
|
|
|
1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
0 |
|
|
|
1 |
|
|
0 |
|
|
1 |
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
— |
|
|
|
|
— |
|
|
|
— |
|
|
1 |
|
|
1 |
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
— |
|
|
|
|
— |
|
|
|
— |
|
|
1 |
|
|
1 |
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
— |
|
|
|
|
— |
|
|
|
— |
|
|
1 |
|
|
1 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
— |
|
|
|
|
— |
|
|
|
— |
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|||||
Запишем и упростим СКНФ для y(t):
y(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t)
Si1(t) Si2(t) x1(t) x2(t) Si1(t) x1(t) Si2(t) x2(t).
Запишем и упростим СДНФ для Si1(t)и ее отрицание для Si2(t 1):
Si1(t 1) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t)
Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t)
Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x2(t) Si1(t) Si2(t) x1(t)
Si1(t) Si2(t) x1(t) Si2(t) x2(t) Si1(t) Si2(t) x1(t).
Запишем систему канонических уравнений: |
|
|
|
|
|
|
|
|
|
Si2(t 1) Si1(t 1). |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
y(t) S1(t) x (t) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
S2 |
(t) x (t), |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
i |
|
1 |
|
|
i |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
2 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
(t) x1(t), |
(14) |
||||||||||||||||
Si (t 1) Si |
(t) x2(t) Si (t) Si |
|
||||||||||||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
2 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
||||
(t 1) S |
(t) x |
|
|
(t) S |
(t) x (t). |
|
||||||||||||||||||
S |
|
(t) S |
|
|
|
|||||||||||||||||||
i |
|
|
i |
2 |
|
|
i |
|
|
i |
|
1 |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
32 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Доопределим каноническую таблицу согласно уравнениям (15):
|
1 |
|
2 |
|
x (t) |
|
x |
2 |
(t) |
y(t) |
1 |
|
2 |
|
||
|
Si |
(t) |
Si |
(t) |
|
1 |
|
|
|
|
Si |
(t 1) |
Si |
(t 1) |
||
|
|
0 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|
0 |
|
1 |
|
|
|
0 |
|
|
0 |
|
0 |
|
|
1 |
1 |
|
1 |
|
0 |
|
|
|
0 |
|
|
0 |
|
1 |
|
|
0 |
1 |
|
0 |
|
1 |
|
|
|
0 |
|
|
0 |
|
1 |
|
|
1 |
1 |
|
1 |
|
0 |
|
|
|
0 |
|
|
1 |
|
0 |
|
|
0 |
0 |
|
0 |
|
1 |
|
|
|
0 |
|
|
1 |
|
0 |
|
|
1 |
0 |
|
0 |
|
1 |
|
|
|
0 |
|
|
1 |
1 |
|
|
0 |
1 |
|
0 |
|
1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
1 |
|
|
0 |
|
|
1 |
1 |
|
|
1 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
0 |
|
|
1 |
|
|
0 |
0 |
|
|
0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
0 |
|
|
1 |
|
|
0 |
0 |
|
|
1 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
0 |
|
|
1 |
|
|
0 |
1 |
|
|
0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
0 |
|
|
1 |
|
|
0 |
1 |
|
|
1 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
1 |
|
|
1 |
|
|
1 |
0 |
|
|
0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
1 |
|
|
1 |
|
|
1 |
0 |
|
|
1 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
1 |
|
|
1 |
|
|
1 |
1 |
|
|
0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
1 |
|
|
1 |
|
|
1 |
1 |
|
|
1 |
|
|
|||||
Пример 12. |
y(t) x1(t) x2(t 1), |
|
|
y(1) 1. |
|
|
|
|
||||||||
Решение. Входной алфавит автомата {00;01;10;11} так как на входе двухэлементные последовательности x1(t)x2(t). Выходной алфавит автомата {0;1}. Выходное значение определяется символом, введенным на предыдущем такте, причем, только второй буквой, и первой буквой символа текущего такта. На каждом такте необходимо знать вторую букву слова, введенного на предыдущем такте, так как вариантов всего два, то и состояний потребуется два (не считая начального). Уточним формулы для вычисления выходного значения в каждом состоянии:
S1 «x2(t 1) 0»: y(t) x1(t) 0 x1(t); S2 «x2(t 1) 1»: yt() x1(t) 1 1.
Построим диаграмму Мура (рисунок 13).
Следуя диаграмме Мура, составим таблицу переходов-выходов:
|
x(t) |
00 |
01 |
10 |
11 |
S |
|
||||
|
S0 |
S1 |
S2 |
S1 |
S2 |
|
1 |
1 |
1 |
1 |
|
|
|
||||
|
S1 |
S1 |
S2 |
S1 |
S2 |
|
0 |
0 |
1 |
1 |
|
|
|
||||
|
S2 |
S1 |
S2 |
S1 |
S2 |
|
1 |
1 |
1 |
1 |
|
|
|
||||
|
|
|
33 |
|
|
Рисунок 13.
Состояния S0 и S2 идентичны, следовательно, их можно отождествить:
Поставим в соответствие состояниям символы «0» и «1: S0 0, |
S1 1. |
|||||||||
Составим каноническую таблицу: |
|
|
|
|
|
|
||||
|
Si (t) |
x1(t) |
|
|
x2(t) |
|
y(t) |
Si (t 1) |
|
|
|
0 |
0 |
|
|
0 |
|
1 |
1 |
|
|
|
0 |
0 |
|
|
1 |
|
1 |
0 |
|
|
|
0 |
1 |
|
|
0 |
|
1 |
1 |
|
|
|
0 |
1 |
|
|
1 |
|
1 |
0 |
|
|
|
1 |
0 |
|
|
0 |
|
0 |
1 |
|
|
|
1 |
0 |
|
|
1 |
|
0 |
0 |
|
|
|
1 |
1 |
|
|
0 |
|
1 |
1 |
|
|
|
1 |
1 |
|
|
1 |
|
1 |
0 |
|
|
Вглядимся в таблицу — значения y(t) соответствуют импликации Si (t) и
x1(t): y(t) Si (t) x1(t) Si (t) x1(t).
Значения Si (t 1)представляют собой отрицания значений x2(t).
|
|
(t) x1(t), |
||
y(t) Si |
||||
Запишем систему канонических уравнений: |
|
|
|
|
S (t 1) x (t). |
||||
|
i |
2 |
|
|
34 |
|
|
|
|
Пример 13. y(t) x1(t) x2(1) x1(t 1), |
y(1) 0. |
Решение. Входной алфавит автомата {00;01;10;11}. Выходной алфавит автомата {0;1}. Выходное значение определяется второй буквой слова, введенного на первом такте, первой буквой слова, введенного на предыдущем такте и первой буквой слова текущего такта. На каждом такте необходимо знать пару символов x2(1), x1(t 1). Уточним формулы для вычисления выходного значения в каждом состоянии:
S1 «x2(1) 0, |
x1(t 1) 0 |
»: y(t) x1(t) 0 0 0; |
|||||
S2 |
«x2(1) |
0, |
x1(t 1) 1 |
»: y(t) x1(t) 0 1 |
0 |
;. |
|
S3 |
«x2(1) |
1, |
x1(t 1) |
0 |
»: y(t) x1(t) 1 0 |
0 |
; |
S4 |
«x2(1) |
1, |
x1(t 1) |
1»: y(t) x1(t) 1 1 x1(t). |
|||
Построим диаграмму Мура (рисунок 14).
Рисунок 14.
Следуя диаграмме Мура, составим таблицу переходов-выходов:
35
Состояния S1 и S2 идентичны, следовательно, их можно отождествить:
Закодируем состояния: S0 S01S02 00, S1 S11S12 01, S3 S31S32 10, S4 S41S42 11.
Составим каноническую таблицу
1 |
2 |
|
x (t) |
x |
2 |
(t) |
y(t) |
1 |
|
2 |
|
||
Si |
(t) |
Si |
(t) |
|
1 |
|
|
|
Si |
(t 1) |
Si |
(t 1) |
|
|
0 |
|
0 |
0 |
|
0 |
0 |
|
0 |
|
1 |
||
|
0 |
|
0 |
0 |
|
1 |
0 |
|
1 |
|
1 |
||
|
0 |
|
0 |
1 |
|
0 |
0 |
|
0 |
|
1 |
||
|
0 |
|
0 |
1 |
|
1 |
0 |
|
1 |
|
1 |
||
|
0 |
|
1 |
0 |
|
0 |
0 |
|
0 |
|
1 |
||
|
0 |
|
1 |
0 |
|
1 |
0 |
|
0 |
|
1 |
||
|
0 |
|
1 |
1 |
|
0 |
0 |
|
0 |
|
1 |
||
|
0 |
|
1 |
1 |
|
1 |
0 |
|
0 |
|
1 |
||
|
1 |
|
0 |
0 |
|
0 |
0 |
|
1 |
|
0 |
||
|
1 |
|
0 |
0 |
|
1 |
0 |
|
1 |
|
0 |
||
|
1 |
|
0 |
1 |
|
0 |
0 |
|
1 |
|
1 |
||
|
1 |
|
0 |
1 |
|
1 |
0 |
|
1 |
|
1 |
||
|
1 |
|
1 |
0 |
|
0 |
0 |
|
1 |
|
0 |
||
|
1 |
|
1 |
0 |
|
1 |
0 |
|
1 |
|
0 |
||
|
1 |
|
1 |
1 |
|
0 |
1 |
|
1 |
|
1 |
||
|
1 |
|
1 |
1 |
|
1 |
1 |
|
1 |
|
1 |
||
|
|
|
|
|
|
|
|
36 |
|
|
|
|
|
Запишем и упростим СДНФ для y(t):
y(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t).
Запишем и упростим СКНФ для Si1(t 1):
Si1(t 1) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t)
Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t) Si1(t) Si2(t) x1(t) x2(t)
Si1(t) Si2(t) x2(t) Si1(t) Si2(t) x1(t) Si1(t) Si2(t) x1(t) Si1(t) x2(t) Si1(t) Si2(t) x1(t) .
Можно заметить, что первые восемь значений в столбце Si2(t 1) равны 1, а затем совпадают со столбцом x1(t). Эту зависимость можно выразить
формулой Si2(t 1) Si1(t) x1(t).
Запишем систему канонических уравнений:
y(t) Si1(t) Si2(t) x1(t),
Si1(t 1) Si1(t) x2(t) Si1(t) Si2(t) x1(t) ,
Si2(t 1) Si1(t) x1(t).
Пример 14. y(t) x2(t) x1(t 2), y(1) x2(1), y(2) x2(2).
Решение. Входной алфавит автомата {00;01;10;11}. Выходной алфавит автомата {0;1}. Выходное значение определяется первой буквой слова, введенного два такта назад и второй буквой слова текущего такта. На каждом такте необходимо знать пару символов x1(t 2), x1(t 1). Символ предыдущего такта нужен, поскольку после введения новых данных эта последовательность сдвинется и x1(t 1) уже будет играть роль x1(t 2).
Итак, нужны два состояния, в которые автомат переходит после первого такта пока x1(t 2) еще невозможно определить. Затем, нужны четыре состояния соответствующие последовательностям x1(t 2), x1(t 1).
S3 «x1(t 2) 0, x1(t 1) 0»: y(t) x2(t) 0 x2(t); S4 «x1(t 2) 0, x1(t 1) 1»: y(t) x2(t) 0 x2(t);. S5 «x1(t 2) 1, x1(t 1) 0»: y(t) x2(t) 1 x2(t);
S6 «x1(t 2) 1, x1(t 1) 1»: y(t) x2(t) 1 x2(t).
Построим диаграмму Мура (рисунок 15).
37
Рисунок 15.
Составим таблицу переходов-выходов:
Состояния S1 и S3 и состояния S2 и S4 попарно идентичны, следовательно, их можно отождествить:
38
Состояния S0 и S1 идентичны, их можно отождествить:
Поставим в соответствие состояниям последовательности «0» и «1»:
S |
S1S2 00, |
S |
2 |
S1S2 |
01, |
S S1S |
2 |
10, |
|
S |
S1S2 11. |
||||||||||||||||||||
0 |
0 |
0 |
|
|
|
2 |
2 |
|
|
|
|
5 |
|
5 |
|
5 |
|
|
|
|
6 |
6 |
6 |
|
|||||||
Составим каноническую таблицу |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
1 |
|
|
2 |
|
|
x (t) |
|
|
x |
2 |
(t) |
|
y(t) |
|
|
1 |
|
|
|
|
|
|
|
2 |
|
|
||||
|
Si (t) |
|
Si (t) |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
Si (t 1) |
|
|
Si (t 1) |
|
||||||||||
|
0 |
|
|
0 |
|
|
0 |
|
|
|
0 |
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
||||
|
0 |
|
|
0 |
|
|
0 |
|
|
|
1 |
|
1 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
||||
|
0 |
|
|
0 |
|
|
1 |
|
|
|
0 |
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
1 |
|
|
||||
|
0 |
|
|
0 |
|
|
1 |
|
|
|
1 |
|
1 |
|
|
|
|
|
0 |
|
|
|
|
|
1 |
|
|
||||
|
0 |
|
|
1 |
|
|
0 |
|
|
|
0 |
|
0 |
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
||||
|
0 |
|
|
1 |
|
|
0 |
|
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
||||
|
0 |
|
|
1 |
|
|
1 |
|
|
|
0 |
|
0 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
||||
|
0 |
|
|
1 |
|
|
1 |
|
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
||||
|
1 |
|
|
0 |
|
|
0 |
|
|
|
0 |
|
1 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
||||
|
1 |
|
|
0 |
|
|
0 |
|
|
|
1 |
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
||||
|
1 |
|
|
0 |
|
|
1 |
|
|
|
0 |
|
1 |
|
|
|
|
|
0 |
|
|
|
|
|
1 |
|
|
||||
|
1 |
|
|
0 |
|
|
1 |
|
|
|
1 |
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
1 |
|
|
||||
|
1 |
|
|
1 |
|
|
0 |
|
|
|
0 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
||||
|
1 |
|
|
1 |
|
|
0 |
|
|
|
1 |
|
0 |
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
||||
|
1 |
|
|
1 |
|
|
1 |
|
|
|
0 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
||||
Значения |
1 |
|
|
1 |
|
|
1 |
|
|
|
1 |
|
0 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
||||
в столбце y(t) |
можно |
выразить как неравнозначность первого и |
|||||||||||||||||||||||||||||
|
y(t) S1(t) x |
|
(t) S1(t) |
|
|
|
|
|
|
|
|||||||||||||||||||||
четвертого столбцов: |
|
|
|
|
|
|
|
S1(t) |
x (t). |
|
|
||||||||||||||||||||
|
x |
(t) |
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
i |
|
|
|
2 |
|
i |
|
|
2 |
|
|
|
|
i |
2 |
|
|
|||||||
Столбец Si1(t 1) |
повторяет столбец |
Si2(t), а столбец Si2(t 1) |
— столбец |
||||||||||||||||||||||||||||
x1(t). Запишем систему канонических уравнений: |
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
y(t) S1(t) |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S1(t) |
x (t), |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
x (t) |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
2 |
|
|
|
|
|
i |
2 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
(t), |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
Si |
|
(t 1) Si |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
(t 1) x1(t). |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
Si |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
39
Примерыпостроенияк.д.а.Мура.
Во всех задачах построить к.д.а., реализующий функцию: определить алфавиты, построить таблицу и диаграмму Мура, построить каноническую таблицу, канонические уравнения.
Пример 15. y(t) 1010101010....
Решение. Входной алфавит у автомата фактически отсутствует. Выходной алфавит автомата {0;1}. Состояний у автомата два – в одном (начальном) на выходе генерируется символ «1», в другом — «0». Построим диаграмму Мура (рисунок 16).
Рисунок 16.
Следуя диаграмме Мура, составим таблицу переходов-выходов:
S |
S1 |
|
S0 |
||
1 |
||
|
||
S1 |
S0 |
|
0 |
||
|
Поставим в соответствие состояниям «0» и «1»: S0 0, |
S1 1. |
|||||||||
Составим каноническую таблицу |
|
|
|
|
|
|
||||
|
Si (t) |
|
y(t) |
|
|
Si2(t 1) |
|
|
||
|
0 |
|
1 |
|
1 |
|
|
|||
|
|
|
0 |
|
0 |
|
|
|||
|
1 |
|
|
|
|
|||||
Запишем систему канонических уравнений: |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(t), |
|
|||||
|
y(t) Si |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S (t 1) S (t). |
|
||||||||
|
|
i |
|
|
i |
|
||||
Пример 16. y(t) 1010001010001010001....
Решение. Состояний у автомата шесть — это определяется длиной повторяемой части последовательности: 101000. Построим диаграмму Мура (рисунок 17).
40