Распознающие автоматы

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

Пример: Автомат, распознающий слова содержащие попарное вхождение букв а

и b, вроде aabbbbaa. f1, f2 - конечные состояния

2 a

a

b f1

a,b a a

4 1

b

a b

b f2

b

.

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

B

a,b b

A b F

a a

C

	A	B	C	F
a	B,C		F
b	B	С,F

Кстати, строка, приписывающая состояниям выходные сигналы совсем не обязательна.

Представление этого автомата с помощью автоматной грамматики:

A ® aB | bB | aC

B ® bC | b

C ® a

Это праворекурсивная автоматная грамматика.