7.5. Минимальные автоматы определение

Автоматы ₁ = (A, B, Q₁, ₁, ₁) и ₂ = (A, B, Q₂, ₂, ₂) называются эквивалентными, если выполняются соотношения:

1.  q_r  Q₁  q_s  Q₂( );

2.  q_s  Q₂  q_r  Q₁( ).

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

Упражнение

1. Показать, что автоматы ₁ и ₂ эквивалентны тогда и только тогда, когда множества функций, вычисляемых этими автоматами из различных состояний как начальных, совпадают.

2. Показать, что всякий автомат эквивалентен самому себе.

ОПРЕДЕЛЕНИЕ

Автомат, все состояния которого являются отличимыми, называется минимальным автоматом.

Пусть  = (A, B, Q, , )  некоторый автомат.

Обозначим как * функцию *: A^* Q Q, которая для любого входного слова и состояния q_i принимает значение, равное состоянию  после переработки из начального состояния q_i.

Эта функция может быть определена следующими соотношениями:

1.  a  A (*(a, q_i) = (a, q_i));

2.   A^*, a  A (* ( a, q_i) = (a, *( , q_i))).

Замечание. Функцию * можно использовать для определения функций, вычисляемых автоматами.

Функция может быть задана соотношениями:

1.  a  A ( (a) = (a, q_i));

2.   A^*, a  A( ( a)= ( ) (a, *( ,q_i)).

Лемма 4

Если состояния q_i и q_j автомата  неотличимые, то для всякого входного слова состояния *( , q_i) и *( , q_j) также являются неотличимыми.

Доказательство

Предположим противное. Пусть q_i и q_j-неотличимые состояния, но для некоторого входного слова состояния * ( , q) и * ( , q_j) являются отличимыми.

Пусть  такое входное слово, на котором различаются *( , q_i) и *( , q_j).

Тогда состояния q_i и q_j различаются на входном слове . Последнее заключение противоречит предположению о неотличимости состояний q_i и q_j.

Лемма доказана.

ТЕОРЕМА 7.5

Для всякого автомата  существует эквивалентный ему минимальный автомат.

Доказательство

1. Построение минимального автомата

Пусть  = (A, B, Q, , )  это произвольный автомат и Q = {q₁, ... , q_n}. Отношение неотличимости состояний автомата  разбивает Q на классы неотличимых состояний: Q₁, ..., Q_d.

Определим множество состояний Q^ = {q¹, . . . , q^d}. Содержательно всякое состояние qⁱ соответствует классу неотличимых состояний Q_i.

Определим две вспомогательные функции

: Q  {1, . . . , d} и : {1, . . . , d}  {1, . . . , n}следующими соотношениями:

1.  q_j  Q ((q_j) = i  q_j  Q_i);

2.  j = 1, . . . ,d ((j) = i  i = ).

Отображение  преобразует состояния автомата  в номера классов неотличимых состояний, содержащих эти состояния.

Отображение  сопоставляет всякому классу неотличимых состояний состояние этого класса с наименьшим индексом.

Определим автомат  = (A, B, Q^, , ). Функции  и  этого автомата задаются соотношениями:

1.  a  A, qⁱ  Q^((a, qⁱ) = q^{((a,q  (i))});

2.  a  A, qⁱ  Q^((a, qⁱ) = (a,q_(i))).

То есть всякий шаг работы автомата  из состояния qⁱ для произвольного входного символа аналогичен шагу работы автомата  из состояния q_(i) для такого же входного символа.

Указанное соответствие представлено на рис.7.8.

Q _i

q_(i) qⁱ

 

a((a,q_(i))) a((a,q_(i)))

Q_r

(a,q_(i)) q^r

Рис.7.8

При этом новое состояние q^r автомата  определяется классом Q_j состояний автомата , который содержит состояние (a,q_(i)).