7.6. Распознавание слов автоматами

Пусть  = (A, B, Q, , )  некоторый автомат и q₀  начальное состояние , а D  Q  множество состояний, называемых распознающими состояниями.

Тогда автомат  распознает входное слово , если после переработки из состояния q₀ он оказывается в состоянии из множества D. Способность конечных автоматов распознавать слова из заданных множеств слов делает возможным применение автоматов в качестве устройств, проверяющих правильность входных слов автоматов.

Определение

Множество U A^* распознается автоматом  из начального состояния q₀ и множества D Q  распознающих состояний, если

  A^* (  U  распознает ).

Например. Если A = {o, s}, то множество слов в этом алфавите, имеющих вид: ₁ sos ₂, где ₁ и ₂  это произвольные слова из A^*, распознается автоматом, изображенным на рис.7.10. В приведенной на этом рисунке диаграмме не отображены сведения о значениях вункции выхода автомата, поскольку они не влияют на процесс распознавания

о

q₀

s o s, o

s q₁ q₃

o q₂ s

Рис.7.10

Здесь q₀  начальное состояние автомата, а {q₃}  множество распознающих состояний.

Состояние q₀ соответствует ситуации, когда поступившая на вход автомата часть перерабатываемого слова не заканчивается никаким началом слова вида sos ₂.

Тогда состояние q₁ соответствует ситуации, когда последний поступивший на вход символ может быть первым в слове sos, q₂ соответствует случаю, когда два последних символа это so. Наконец, q₃ соответствует случаю, когда на входе автомата уже появились последовательно все символы слова sos .

Заметим, что для распознавания слов конечными автоматами значения символов на выходе автомата несущественны.

Поэтому в диаграмме из приведенного примера дуги не размечены значениями выходных символов.

В дальнейшем автомат  = (A, B, Q, , ), который распознает множество слов U из начального состояния q₀ для множества распознающих состояний D, будем записывать как  = (A, Q, , q₀, D).

Если некоторое множество U A^*распознается некоторым конечным автоматом, то U называется автоматным языком.

ТЕОРЕМА 7.6

Множество автоматных языков замкнуто относительно операций объединения, пересечения, разности и дополнения языков.

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

Пусть языки U₁ и U₂ распознаются автоматами

₁ = (A, Q₁, ₁, q₀, D₁) и ₂ = (A, Q₂, ₂, q₁, D₂).

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

Определим автомат  как (A, Q₁ Q₂, , (q₀, q₁), D), где D обозначает множество состояний, которое будет выбираться так, чтобы обеспечить распознавание множеств U₁  U₂, U₁  U₂, и U₁ \ U₂.

Состояния   это пары (q_i, q_j), где q_i  Q₁ и q_j  Q₂. Начальным состоянием  является состояние (q₀, q₁). Функция перехода  представляет собой пару функций (₁, ₂), каждая из которых определяет значение соответствующей компоненты состояния . То есть, если в момент времени t автомат находится в состоянии (q(t), q(t)), то значение состояния  в момент t+1 равно (₁(x(t), q(t)), ₂(x(t), q(t))).

Тогда автомат  из начального состояния (q₀, q₁) распознает множество U₁  U₂, если в качестве множества распознающих состояний D выбрано множество

D₁ Q₂  Q₁ D₂.

Действительно, при переработке произвольного входного слова из начального состояния (q₀, q₁) компоненты состояния автомата  изменяются так же, как состояния автоматов ₁ и ₂, когда эти автоматы перерабатывают из состояний q₀ и q₁ соответственно.

Поэтому  заканчивает переработку в состоянии из D тогда и только тогда, когда автомат ₁ заканчивает переработку в состоянии из D₁ или ₂ заканчивает переработку этого же слова в состоянии из D₂.

То есть U₁  U₂  заканчивает переработку этого слова в состоянии из множества D₁ Q₂  Q₁ D₂.

Аналогично можно показать, что если в качестве множества распознающих состояний взять D₁ D₂, то автомат  из начального состояния (q₀, q₁) распознает U₁  U₂.

Множество U₁ \ U₂ распознается конечным автоматом , для которого D = D₁ (Q₂ \ D₂).

Если множество слов U распознается автоматом

 = (A, Q, , q₀, D), то A^* \ U распознается автоматом

(A, Q, , q₀, Q \ D).

Доказательство окончено.

Упражнение. Показать, что множество всех симметричных слов в алфавите {0, 1} не является автоматным.