Автоматы-распознаватели

АВТОМАТЫ И ГРАММАТИКИ

Конечный автомат - распознаватель это объект вида M=áT, Q, s₀, D, Fñ , состоящий из пяти следующих компонент:

1. T= {a₁, … ,a_m} (m ³1) – конечное множество, представляющее собой входной алфавит автомата.

2. Q={s₀, … ,s_n-1} (n ³1) - конечное множество состояний, в которых может находиться автомат (точнее, его управляющее устройство) в момент «считывания» очередного символа (это тоже некий алфавит);

3. s₀ – выделенное начальное состояние автомата, s₀ Î Q. В этом состоянии автомат находится, когда поступает для анализа новое входное слово.

4. D- множество заключительных или допускающих состояний автомата, DÍ Q.

5. F – функция перехода или система команд автомата. .

Если найдется такая последовательность переходов из одного состояния в другое, что в результате прочтения входного слова автомат М окажется в одном из заключительных состояний, то мы говорим, что автомат М распознает (допускает) это слово в алфавите T.

Если же такой последовательности переходов найти не удалось, слово автоматом не распознается.

Каждое допускающее состояние отмечается на диаграмме двойным кружком: .

Пример.

Автомат допускает (распознает) слова baa, abbba, bb,

но не распознает слова bbb, abab, abb.

Пример.

Автомат допускает (распознает) слова:

bb, aababaaa, baaab, babaaa, aabaabaa,…

Автомат может прочесть любое слово языка, заданное регулярным выражением

a*ba*ba*.

Или такой язык можно описать как множество всех слов, содержащих точно два b.

Состояние s₄ является примером состояния зацикливания.

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

Пример.

Параллельные переходы можно изображать одной стрелкой. При этом метки переходов перечисляют через запятую. Упрощенный вид:

Автомат допускает (распознает) только слова ab, ac. Этот язык можно задать с помощью регулярного выражения

.

Пример.

Каждое слово следует начинать с ab и заканчивать на c.

Однако, учитываю петлю aabc, которая начитается и заканчивается в s4, получаем регулярное выражение для автомата

.

Пример

Так как при чтении трех последовательных b автомат переходит вs₃, а все остальные – финальные состояния, то язык, который допускает автомат, состоит из всех слов, не включающих три последовательных b.

Рассмотренные автоматы являются детерминированными автоматами.

Определение. Детерминированный конечный автомат – автомат, из одного состояния которого не может выходить несколько переходов (стрелок), помеченных одним и тем же символом.

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

Соответственно, после прочтения слова можно сразу сказать, допустимо оно или нет.