Лекция: Распознающие автоматы
Распознающим называется автомат Мура с множеством выделенных состояний, называемых конечными. Говорят, что автомат распознает входное слово, если, начав свою работу в одном из начальных состояний, он заканчивает ее в одном из конечных.
Пример: Автомат, распознающий слова содержащие попарное вхождение букв а
и 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
Это праворекурсивная автоматная грамматика.