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

Скінченним автоматом називається система S={A, Q, V, }, у якої A={a₁,…,a_m},Q={q₁,…q_n},V={v₁,…,v_k}- скінченні множини (алфавіти); a : Q x A  Q і : Q x A  V - функції, визначені на цих множинах. А називається вхідним алфавітом, V - вихідним алфавітом, Q - алфавітом стану;  - функцією переходів,  - функцією виходів. Якщо, крім того, в автоматі S виділено один стан, який називається початковим (будемо вважати, що цей стан q₀), то отриманий автомат називається ініціальним і позначається ( S, q₀ ) ; таким чином, по неініціальному автомату з n станами можна n різноманітними способами визначити ініціальний автомат.

Оскільки функції  і визначені на скінченних множинах, їх можна задавати таблицями. Звичайно дві таблиці зводяться в одну таблицю  і , яка називається таблицею переходів-виходів автомата або автоматною таблицею.

Ще один поширений і наочний спосіб завдання автоматів - орієнтований мультиграф, називаний графом переходів або діаграмою переходів. Вершини графа відповідають станам; якщо  (q_i, a_j) = q_k і (q_i, a_j)= v_l, то з q_i у q_k йде ребро, на якому написані a_j і v_l .Кратні ребра не обов'язкові; наприклад два ребра з q₂ у q₁ можна замінити одним, на якому будуть написані обидві пари a₃/v₁ і a₂/v₁ . Для будь-якого графа переходів у кожній вершині q_i виконані такі умови, що називаються умовами коректності:

1) для будь-якої вхідної букви a_i є ребро, що виходить із q_i, на якому написане a_j (умовна повнота);

2) будь-яка буква a_j зустрічається тільки на одному ребрі, що виходить із q_i (умова несуперечності або детермінованості).

Виконаємо синтез кінцевого автомату по заданій сумісній таблиці переходів-виходів:

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

1)Складемо так звану проміжну таблицю.

A	0	0	0	1	1	1	2	2	2	3	3	3
Qn	0	1	2	0	1	2	0	1	2	0	1	2
Q(n+1)	1	0	2	1	2	0	0	0	1	2	2	1
V	0	0	1	1	1	0	1	0	1	0	0	1

2) За складеною таблицею необхідно створити граф кінцевого автомату.

Рис. 3.1 Графічне представлення заданого кінцевого автомату

3) Таблиця істинності для даного кінцевого автомату.

A		Qn		Q(n+1)		Y
A1(n)	A2(n)	Q1(n)	Q1(n)	Q 1(n+1)	Q 2(n+1)
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1	0 0 1 * 0 1 0 * 0 0 0 * 1 1 0 *	1 0 0 * 1 0 0 * 0 0 1 * 0 0 1 *	0 0 1 * 1 1 0 * 1 0 1 * 0 0 1 *

4) Побудуєто карту Карно для отриманих нами функцій Y, Q _1(n+1) та Q_2(n+1)

Для Q_1(n+1)

Q1,Q2 A1,A2	00	01	11	10
00			*	1
01		1	*
11	1	1	*
10			*

Q_1(n+1) = Q_1(n) Q_2(n) v A₁ A₂ v A₂ Q_2(n)

Для Q_2(n+1)

Q1,Q2 A1,A2	00	01	11	10
00	1		*
01	1		*
11			*	1
10			*	1

Q_2(n+1) = Q_1(n) Q_2(n) v Q_1(n) Q_2(n) v A₁ Q_1(n) Q_2(n)

Для Y

Q1,Q2 A1,A2	00	01	11	1 0
00			*	1
01	1	1	*
11			*	1
10	1		*	1

Y = Q_1(n) Q_2(n) v A₂ v A₁ v Q_1(n) Q_2(n)

5) Структурна схема кінцевого автомату має такий вигляд

Таким чином, отриманий кінцевий автомат містить:

9 елементів – і;

4 елементи – або та 2 елемента пам’яті.

Розділ 4.