полученных пар совместимых состояний можно образовать максимальные классы совместимости, то есть классы в которые нельзя добавить ни одного состояния. Нетрудно понять, что система всех максимальных классов является полной и замкнутой (для любой совместимой пары q, q0δ(q, a) и δ(q0, a) также совместимы и, следовательно, лежат по крайней мере в одном максимальном классе), поэтому ей соответствует автомат S0, покрывающий исходный автомат S. Однако в общем случае он может иметь даже больше состояний, чем S.

Распознавание множеств автоматами

Автоматы Мура

Конечный автомат называется автоматом Мура, если его функция выходов зависит только от состояний, то есть для любых q, ai, aj λ(q, ai) = λ(q, aj). Функцию выходов автомата Мура естественно считать одноаргументной функцией; обычно ее обозначают буквой µ и называют функцией отметок (так как она каждому состоянию однозначно ставит в соответствие отметку-выход). В графе автомата Мура выход пишется не на ребрах, а при вершине. Общая модель конечного автомата, которая рассматривалась ранее, называется автоматом Мили. Несмотря на то, что автомат Мура — частный случай автомата Мили, возможности этих двух видов автоматов совпадают.

Теорема. Для любого автомата Мили существует эквивалентный ему автомат Мура.

Пусть дан автомат Мили S = (A, Q, V, δ, λ), A = {a1, . . . , am}, Q = {q1, . . . , qn}. Определим автомат Мура SM следующим образом: AM = A, Vm = V, Qm содержит mn + n состояний: mn состояний

qij(i = 1, . . . , n; j = 1, . . . , m), соответствующих парам (qi, aj) автомата S, и n состояний qi0(i = 1, . . . , n). Функции δM и µ определяются так: δM (qi0, ak) = qik; для i = 1, . . . , nδM (qij, ak) = qlk, где l таково, что δ(qi, ak) = ql; µ(qi0) не определено; для остальных состояний µ(qij) = λ(qi, aj).

Для доказательства теоремы достаточно показать, что для любого qi и любого αS(qi, α) = SM (qi0, α).

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель