Анализ конечных автоматов. (до90 минут)

Задача анализа конечных автоматов состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства.

Полное описание поведения автомата заключается в определении последовательности выходных сигналов при возбуждении его в тактовые моменты времени некоторой последовательностью входных сигналов. Последовательности сигналов на входе и выходе представляются кортежами символов из входного А и выходного В алфавитов одинаковой длины L, т.е. ½a½=½b½= L, где aÎА*, bÎВ*. Для такого описания автомата, помимо характеристических функций d и l, необходимо определить или задать начальное состояние q₀ÎQ.

Наиболее удобно определять реакцию автомата на входную последовательность по его графу. Для этого достаточно проследить путь в графе, начиная от вершины начального состояния q₀, по направлению дуг, которые отмечены символами входного алфавита А. Выходная последовательность в этом случае будет отмеченный символами В рассматриваемый путь.

Пример: Из графа для входной последовательности a=<2, 0, 1, 1, 2, 3> и начального состояния q₀ имеем выходную последовательность b=<0, 1, 0, 0, 1, 1> (смена состояний автомата в этом случае <1, 3, 0, 2, 2, 3>). При начальном состоянии q₂ и той же входной последовательности a=<2, 0, 1, 1, 2, 3> получаем b=<1, 1, 0, 0, 1, 1>.

С помощью графа автомата легко выделить следующие характерные типы его состояний:

переходящее состояние, из которого можно перейти, по крайней мере, в одно другое состояние, но после этого уже нельзя возвратиться в него ни при каком воздействии (соответствующая вершина не имеет заходящих дуг, но имеет хотя бы одну исходящую дугу).

тупиковое состояние, в которое можно перейти, по крайней мере, из одного другого состояния, но после этого уже нельзя выйти из него ни при каком воздействии (соответствующая вершина не имеет исходящих дуг в другие вершины, но имеет хотя бы одну входящую дугу из другой вершины).

изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния (соответствующая вершина содержит только петлю).

Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние q₀ автомата U принадлежит несущему множеству Q_i состояний, которое составляет тупиковый или изолированный подавтомат, то автомат U можно упростить исключением всех состояний, которые не принадлежат множеству Q_i, и всех дуг, начинающихся в этих состояниях. Пусть U1, U2, U3 – соответственно преходящий, тупиковый и изолированный подавтоматы автомата U, которые характеризуются множествами состояний Q₁, Q₂, Q₃. Очевидно, выделение таких подавтоматов соответствует разбиению множества Q_i состояний автомата U =<A, Q, B, d,l > на непересекающиеся подмножества Q₁, Q₂, Q₃, представляющие собой классы эквивалентности, т.е. Q₁È Q₂ È Q₃=Q, Q₁Ç Q₂ =Æ, Q₂Ç Q₃ =Æ, Q₁Ç Q₃ =Æ.

Пример: Для обобщенного графа

матрица переходов (соединения) автомата может быть представлена в виде:

m11	m12
	m12
		m33

где m_11, m_22, m₃₃ – матрицы подавтоматов U1, U2, U3; m₁₂ – матрица, характеризующая переходы от состояний преходящего подавтомата U1 к состояниям тупикового подавтомата U2. Отсюда следует, что разбиение автомата U на подавтоматы U1, U2, U3 можно осуществить преобразованием его матрицы соединений (переходов) к стандартному виду путем перестановки соответствующих строк и столбцов.

Пример: Для автомата U, заданного графом

Преобразованная матрица соединений имеет вид:

q3	q6	q2	q4	q7	q1	q5
	2,0	0,1		1,1			q3
1,0			1,0	2,1			q6
		1,1Ú2,0		0,0			q2
		1,0Ú2,1	0,0				q4
			0,1Ú2,0	1,0			q7
					0,1	1,0Ú2,1	q1
					0,1Ú1,0Ú2,0		q5

Отсюда следует, что Q1={ q₃, q₆} составляет преходящий подавтомат, Q2={ q₂, q_4, q₇} – тупиковый подавтомат и Q3={ q₁, q₅} – изолированный подавтомат. Если начальное состояние q₀ÎQ принадлежит подмножеству Q2, то можно упростить автомат U, исключив состояния Q₁È Q₃=={ q₃, q₆, q₁, q₅}, т.е. имеем

<A={0,1,2}, Q2={ q₂, q₄, q₇}, B={0,1}, d, l>.

В случае принадлежности начального состояния q₀ подмножеству Q₃ автомат упрощается исключением состояний Q₁È Q₂=={ q₃, q₆, q₂, q₄, q₇ }, т.е

<A={0,1,2}, Q={ q₁, q₅}, B={0,1}, d, l>.

Лекция №9.

Синтез КА

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Текст лекции

Дата добавления: 2015-12-01