Минимизация автомата

Построение детерминированного конечного автомата

Для автоматной грамматики строится таблица переходов недетерминированного автомата (в таблице по строкам расположены состояния, а по столбцам - входные символы, в клетках на пересечении i-й строки и j-го столбца проставляется состояние, в которое переходит автомат из состояния i по приходу входного символа j). Для этого каждому нетерминалу ставится в соответствие некоторое состояние автомата. Затем по грамматике таблица заполняется следующим образом: на пересечении строки состояния, соответствующего нетерминалу левой части правила, и столбца, соответствующего терминальному символу, ставится состояние, соответствующее нетерминальному символу правой части правила. Если нетерминал в правой части отсутствует, то в клетке таблицы ставится заключительное состояние, которое вводится дополнительно к уже имеющимся состояниям.

Приведение недетерминированного автомата

к детерминированному виду

Детерминированным конечным автоматом называется конечный автомат, любая клетка таблицы переходов которого не содержит несколько состояний. В пустой клетке подразумеваем состояние ошибки.

Процедура приведения недетерминированного конечного автомата к детерминированному (по таблице переходов) сводится к следующему:

1. Определяется клетка, в которой содержится 2 или более состояний

(например, qi и qj).

2. Строка i и строка j накладываются друг на друга, и в таблице переходов появляется новая склеенная строка, соответствующая новому состоянию q_{i, j}.

3. Если состояние qi или qj стоит отдельно или в комбинации с другими состояниями еще в какой-либо клетке таблицы, то соответствующая строка i или j сохраняется в таблице, иначе - убирается из таблицы после склеивания.

Продемонстрируем изложенное на примере:

Таблица 3

	Состояние	x0	x1	x2	x3	x4	x5	x6	x7
q0	S (нач. сост.)					q15	q3	q7,q9	q6
q1	A	q4				q15
q2	B	q5				q15
q3	C	q5				q15
q4	D	q15				q0
q5	E	q15				q0
q6	F		q11			q12		q14
q7	S1					q8
q8	S2					q1
q9	S3							q10
q 10	S4			q2
q 11	S5			q12
q 12	S6						q13
q 13	S7		q15
q 14	S8								q13
q 15	закл. сост.

Склеиваем состояния q7 и q9 в состояние q7,9. В итоге, получаем таблицу 4:

Таблица 4

	Состояние	x0	x1	x2	x3	x4	x5	x6	x7
q0	S (нач. сост.)					q15	q3	q7,9	q6
q1	A	q4				q15
q2	B	q5				q15
q3	C	q5				q15
q4	D	q15				q0
q5	E	q15				q0
q6	F		q11			q12		q14
q7,9	S1					q8		q10
q8	S2					q1
q 10	S4			q2
q 11	S5			q12
q 12	S6						q13
q 13	S7		q15
q 14	S8								q13
q 15	закл. сост.

Теорема. Для любого автомата существует минимальный автомат единственный с точностью до изоморфизма.

Рассмотрим алгоритм минимизации автомата по методике Мура:

1. В таблице переходов автомата отыскиваются строки, у которых имеются рабочие состояния в одинаковых столбцах. Под рабочим состоянием будем понимать состояние, отличное от состояния ошибки. Состояние ошибки на таблице переходов обозначено пустой клеткой. Состояния, соответствующие таким строкам, заносятся в группы.

2. Рабочие состояния внутри группы проверяются на эквивалентность.

Два состояния qi и qj называются эквивалентными, если для любого

входного символа Xk функции выходов и функции переходов пар

(qi, Xk), (qj, Xk) будут равны.

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

Удаляем из таблицы строку состояния q9, так как на состояние q9 нет больше переходов. Cтроку состояния q7 заменяем на склеенную строку q7,9, так как на состояние q7 нет больше переходов. Состояния

q1, q2, q3 - эквивалентны, удаляем строки q2 и q3. Заменяем в таблице 5 все q2 и q3 на q1. Состояния q4 и q5 - эквивалентны, удаляем строку q5, соответственно q5 в таблице 4 заменяем на q4. В итоге, получаем таблицу 5:

Таблица 5

	Состояние	x0	x1	x2	x3	x4	x5	x6	x7
q0	S (нач. сост.)					q15	q1	q7,9	q6
q1	A	q4				q15
q4	D	q15				q0
q6	F		q11			q12		q14
q7,9	S1					q8		q10
q8	S2					q1
q 10	S4			q1
q 11	S5			q12
q 12	S6						q13
q 13	S7		q15
q 14	S8								q13
q 15	закл. сост.				q0

Продолжим рассматривать решение в соответствии с обозначенным алгоритмом.Анализ делаем по табл. 4. Группы состояний, проверяемые на эквивалентность, следующие:

(q1;q2;q3), (q₄; q_5,).

Проведем анализ этих состояний по переходам. Устанавливаем, что состояния q1, q2 и q3, а также состояния q4 и q5 являются эквивалентными по определению. Обозначив эквивалентные состояния одним состоянием, введем новые нетерминальные символы r вместо q. Будем иметь:

r0 = q0; r1 = q1; r2 = q₄; r3 = q6; r4 = q_7,9;

r5 = q8; r6 = q10; r7 = q11; r8 = q₁₂; r9 = q13, r10= q14,

r11=q15;

Введем полученные замены и подстановки в табл.5 переходов автомата. Будем иметь новую таблицу 6 эквивалентную с точностью до изоморфизма таблице переходов 5.

Таблица 6

Соответствие нетерминалов	Терминалы
Х0	Х1	Х2	Х3	Х4	Х5	Х6	Х7
r0 -нач.сост.	q0					r11	r1	r4	r3
r1	q1	r2				r11
r2	q4	r11				r0
r3	q6		r7			r8		r10
r4	q7,9					r5		r6
r5	q8					r1
r6	q10			r1
r7	q11			r8
r8	q12						r9
r9	q13		r11
r10	q14								r9
r11- закл. сост	q15				ro

Дата добавления: 2014-12-07