Мегаобучалка Главная | О нас | Обратная связь  


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




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

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

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

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

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

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

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

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

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

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



Пример.

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

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

Пример.

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

bb, aababaaa, baaab, babaaa, aabaabaa,…

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

a*ba*ba*.

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

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

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

Пример.

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

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

.

Пример.

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

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

.

Пример

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

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

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

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

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

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...
Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация...
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (760)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7