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

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

ТЕОРЕМА 7.5

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

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

Лемма 4

Если состояния q _i и q _j автомата Á неотличимые, то для всякого входного слова состояния j*(, q _i) и j*(, q _j) также являются неотличимыми.

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

Пусть - такое входное слово, на котором различаются j*(, q _i) и j*(, q _j).

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

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

Пусть Â = (A, B, Q, j, y) - это произвольный автомат и Q = { q ₁,..., q _n}. Отношение неотличимости состояний автомата Â разбивает Q на классы неотличимых состояний: Q ₁,..., Q _d.

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

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

h: Q ® { 1,..., d } и x: { 1,..., d } ® { 1,..., n }следующими соотношениями:

1) " q _j Î Q (h(q _j) = i Û q _j Î Q _i);

2) " j = 1,..., d (x(j) = i Û i = ).

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

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

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

1) " a Î A, q ⁱ Î Q ^*(F(a, q ⁱ) = q ^{h(j( a , q x (i))});

2) " a Î A, q ⁱ Î Q ^*(Y(a, q ⁱ) =y(a, q _x(i))).

То есть всякий шаг работы автомата Á из состояния q ⁱ для произвольного входного символа аналогичен шагу работы автомата Â из состояния q _{x( i )} для такого же входного символа.

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

Q _i

q _x(i) q ⁱ

 Á

a (y(a, q_{x (i)})) a (y(a, q_{x (i)}))

Q _r

j(a, q_{x (i)}) q ^r

Рис. 7.8

При этом новое состояние q ^r автомата Á определяется классом Q _j состояний автомата Â, который содержит состояние j(a, q _x(i)).

2. Доказательство минимальности автомата Á

Докажем, что " Î A ^*( () = ()).

Проведем доказательство этого свойства индукцией по длине слова . При этом дополнительно будет доказываться вспомогательное утверждение: если F^*(a, q ⁱ)= q ^r, то j^*(a, q _{x( i )})Î Q_r, а состояния j^*(a, q _{x( i )}) и q _{x( r )} являются неотличимыми.

Дата добавления: 2015-03-31