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

Пусть Á = (A, B, Q, j, y) - некоторый автомат и 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, j, y), который распознает множество слов U из начального состояния q ₀ для множества распознающих состояний D, будем записывать как Â = (A, Q, j, q ₀, D).

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

ТЕОРЕМА 7.6

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

Дата добавления: 2015-11-30