Минимизация числа внутренних состояний конечного автомата.

M_u = {U: T (U) = П } – множество автоматов.

Найти минимальный U Î M(U) такой, что |Q| > |Q'| = n _min, n Î N

U=<A, Q, B, δ, λ>

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

Замечание.

1. Если множество состояний автомата разбивается на р классов эквивалентности, то приведенный автомат имеет р состояний.

p ≤ |Q|

2. Эта теорема не указывает алгоритма нахождения эквивалентных (неотличимых) состояний автомата.

3. Тривиальный путь определения (но не вычисления) неотличимых состояний предполагает перебор по бесконечному множеству входных символов.

4. Наиболее известным для определения классов эквивалентных состояний автомата является алгоритм Мили:

· шаг i. Два состояния автомата q_i, q_j Î Q относим в первый класс C_ij, если для любой буквы входного алфавита функция выходов

λ (q_i, a) = λ (q_j, a)

· шаг i+1. Два состояния из одного класса относим в один класс C_ij → C_i+1,j, если для любого входного символа функция переходов принадлежит этому классу

δ (qi, a) и δ (q_j, a) Î C_ij

· шаг i+2. Если i+1 шаг не изменяет разбиения, т.е. состояние из одного класса C_ijÎC_i+1,j, то алгоритм заканчивается. Получаем разбиение на классы эквивалентных состояний. Оно является искомым.

Пример. Для автомата U=<A, Q, B, δ, λ>, где A={a₁, a₂, a₃}, |Q|=9, B={b₁, b₂}, задана автоматная таблица. Найти минимальный автомат по числу внутренних состояний.

Q \ A	a1	a2	a3
q1	q2,b1	q4,b2	q4,b2
q2	q1,b2	q1,b1	q5,b1
q3	q1,b2	q6,b1	q5,b1
q4	q8,b1	q1,b2	q1,b2
q5	q6,b2	q4,b2	q3,b1
q6	q8,b1	q9,b2	q6,b2
q7	q6,b2	q1,b2	q3,b1
q8	q4,b2	q4,b1	q7,b1
q9	q7,b1	q9,b2	q7,b2

Класс разбиений эквивалентных состояний:

C₁₁={q₁, q₄, q₆, q₉}

C₁₂={q₂, q₃, q₈}

C₁₃={q₅,q₇}

A \ Q	q1	q4	q6	q9	q2	q3	q8	q5	q7
a1	C12	C12	C12	C13	C11	C11	C11	C11	C11
a2	C11	C11	C11	C11	C11	C11	C11	C11	C11
a3	C11	C11	C11	C13	C13	C13	C13	C12	C12

C₂₁={q₁,q₄,q₆}

C₂₂={q₉}

C₂₃={q₂,q₃,q₈}

C₂₄={q₅,q₇}

A \ Q	q1	q4	q6	q9	q2	q3	q8	q5	q7
a1	C23	C23	C23	C24	C21	C21	C21	C21	C21
a2	C21	C21	C22	C22	C21	C21	C21	C21	C21
a3	C21	C21	C21	C24	C24	C24	C24	C23	C23

C₃₁={q₁,q₄}

C₃₂={q₆}

C₃₃={q₉}

C₃₄={q₂,q₃,q₈}

C₃₅={q₅,q₇}

A \ Q	q1	q4	q6	q9	q3	q2	q8	q5	q7
a1	C34	C34	C34	C34	C31	C31	C31	C32	C32
a2	C31	C31	C34	C32	C32	C31	C31	C31	C31
a3	C31	C31	C34	C34	C35	C35	C35	C34	C34

C₄₁={q₁,q₄}

C₄₂={q₆}

C₄₃={q₉}

C₄₄={q₂,q₈}

C₄₅={q₃}

C₄₆={q₅,q₇}

A \ Q	q1	q4	q6	q9	q3	q2	q8	q5	q7
a1	C44	C44	C44	C44	C41	C41	C41	C42	C42
a2	C41	C41	C44	C42	C42	C41	C41	C41	C41
a3	C41	C41	C44	C44	C45	C45	C45	C44	C44

Автоматная таблица приведенного автомата имеет вид

A \ Q	q1	q2	q3	q5	q6	q9
a1	q2,b1	q1,b2	q1,b2	q6,b2	q2,b1	q1,b1
a2	q1,b2	q1,b1	q6,b1	q1,b2	q9,b2	q9,b2
a3	q1,b2	q5,b1	q5,b1	q3,b1	q6,b2	q5,b2

q1 эквивалентно q4

q2 эквивалентно q8

q5 эквивалентно q7

Приведенный автомат содержит 6 классов разбиения, что означает, что минимальный (приведенный) автомат имеет 6 внутренних состояний (вместо 9 исходных). При этом то состояние, которое указано в автоматной таблице, заменено эквивалентным.

Дата добавления: 2015-07-10