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

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

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

Ще один поширений і наочний спосіб завдання автоматів - орієнтований мультиграф, називаний графом переходів або діаграмою переходів. Вершини графа відповідають станам; якщо d (q_i, a_j) = q_k і l (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 (умова несуперечності або детермінованості).

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

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

 

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

 

A

Qn

Q(n+1)

V

 

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)
				* * * *	* * * *	* * * *

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

 

Для Q_1(n+1)

 

Q1,Q2 A1,A2
			*
			*
			*
			*

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
			*
			*
			*
			*

 

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				10
			*
			*
			*
			*

 

 

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

 

 

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

 

 

 

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

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

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

 

Розділ 4.