Автоматы-распознаватели
АВТОМАТЫ И ГРАММАТИКИ Конечный автомат - распознаватель это объект вида 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-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (937)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |