3. Завдання 3.

   1. Синтез кінцевого автомата.

Таблиця переходів-виходів кінцевого автомату (Таблиця 5):

X(n)

S(n) 0 1 2 3

0 0/0 2/1 0/0 2/0

1 1/0 1/1 0/1 2/0

2 2/1 0/0 1/1 1/1

Таблиця 5. «Таблиця переходів-виходів кінцевого автомата»

X(n) – вхід;

S(n) – алфавіт внутрішніх станів;

0/0 – новий стан/вихід;

Перетворимо вихідну таблицю в спеціальну форму з виділенням вхідних-вихідних сигналів і внутрішніх станів (Таблиця 6.):

В ходи X(n) 000 111 222 333

П от. Дані S(n) 012 012 012 012

Н аст. Дані S(n+1) 012 210 001 221

Вихід Y(n) 001 110 011 001

Таблиця 6. «Внутрішні стани та сигнали»

З образимо кінцевий автомат за допомогою графа (Рис.15.):

1. Рис. 15. «Граф кінцевого автомату»

За допомогою таблиці внутрішніх станів та виходів (Таблиця 6.) побудуємо таблицю істинності кінцевого автомату (Таблиця 7.):

X (n)		S (n)			S (n+1)			Y
X1(n)	X2(n)	S1(n)	S2(n)	S1(n+1)		S2(n+1)
0	0	0	0	0		0	0
0	0	0	1	0		1	0
0	0	1	0	1		0	1
0	0	1	1	*		*	*
0	1	0	0	1		0	1
0	1	0	1	0		1	1
0	1	1	0	0		0	0
0	1	1	1	*		*	*
1	0	0	0	0		0	0
1	0	0	1	0		0	1
1	0	1	0	0		1	1
1	0	1	1	*		*	*
1	1	0	0	0		0	0
1	1	0	1	1		0	0
1	1	1	0	1		1	1
1	1	1	1	*		*	*

Таблиця 7. «Таблиця істинності кінцевого автомата»

Синтезований автомат не має внутрішнього стану рівного 3, отже у таблиці істинності строки, які відповідають цьому станові позначені «*», яка означає «байдужість» кінцевого автомата до цього стану, тобто на місці «*» може бути, як «0» так і «1».

Побудуємо карту Карно для Y(n) (Рис.16.):

S1S2 X1X2	00	01	1 1	1 0
00			*	1
01	1	1	*
11			*	1
10		1	*	1

|X₁|X₂S₁

X₁S₁|S₂ Рис.16. «Карта Карно для вихідних даних - Y(n)»

|X₁X₂|S₁ X₁|X₂S₂

Рис.16.

Y(n)=|X₁X₂|S₁ V X₁|X₂S₂ V X₁S₁|S₂ V |X₁|X₂S₁.

Побудуємо карту Карно для S₁(n+1)(Рис.17.):

S1S2 X1X2	00	01	1 1	10
00			*	1
01	1		*
11		1	*	1
10			*

|X₁|X₂S₁

X₁X₂S₁ Рис.17. «Карта Карно для S₁ (n+1) переходів»

|X₁X₂|S₁|S₂ X₁X₂S₂

S₁(n+1)= |X₁X₂|S₁|S₂ V X₁X₂S₂ V X₁X₂S₁ V |X₁|X₂S₁.

Побудуємо карту Карно для S₂(n+1) (Рис.18.):

S1S2 X1X2	00	0 1	11	10
00		1	*
01		1	*
11			*	1
10			*	1

X₁S₁|S₂ Рис.18. «Карта Карно для S₂(n+1) переходів»

|X₁|S₁S₂

S₂(n+1)= |X₁|S₁S₂ V X₁S₁|S₂.

На даному етапі синтезу отримано аналітичні вирази для функції виходу і двох функцій переходів. Представимо структурну схему автомата (Рис.19.):

Комбінаційна

схема

X₁(n) Y(n)

П₁

П₂

X₂(n)

S₂(n) S₂(n+1)

S₁(n+1)

S₁(n)

Рис.19. «Комбінаційна схема кінцевого автомата»

У складі кінцевого автомату присутня комбінаційна схема (Рис.19.)доповнена двома елементами пам’яті, котрі через зворотній зв'язок забезпечують зміну інформації внутрішніх станів кінцевого автомата.

Комбінаційна схема автомата і її зв'язок з елементами показана на наступному рисунку (Рис.20.):

1

1

1

1

&

&

&

&

&

&

&

&

&

&

1

1

X₁ X₂ S₁ S₂ |X₁ |X₂ |S₁ |S₂

Y

Н

Н

(n)

1

S₁(n+1)

S₂(n+1)

П₁

S₁(n+1) П₁

S₂(n+1) П₂ Пам'ять

Рис.20. «Комбінаційна схема автомата»

Таким чином, синтезований автомат містить 4 елементи «ні», 10 елементів «і», 3 елементи «або» та 2 елементи пам’яті.