Математическая теория формальных языков
Недетерминированные конечные автоматы
Определение 2.1.1.
Конечный автомат (finite automaton, finite-state machine) - это пятерка , где - конечный входной алфавит (или просто алфавит) данного конечного автомата, Q и - конечные множества,
, . Элементы Q называются состояниями (state), элементы I - начальными (initial) состояниями, элементы F - заключительными или допускающими (final, accepting) состояниями. Если , то
называется переходом (transition) из p в q, а слово x - меткой (label) этого перехода.
Пример 2.1.2.
Пусть Q = {1,2}, , I = {1}, F = {2},
Тогда - конечный автомат.
Замечание 2.1.3.
Конечные автоматы можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)). На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Стрелка из p в q, помеченная словом x, показывает, что
является переходом данного конечного автомата. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком.
Пример 2.1.4.
На диаграмме изображен конечный автомат из примера 2.1.2.
Замечание 2.1.5.
Если в конечном автомате имеются несколько переходов с общим началом и общим концом, то такие переходы называются параллельными. Иногда на диаграмме состояний конечного автомата параллельные переходы изображают одной стрелкой. При этом метки переходов перечисляют через запятую.
Пример 2.1.6.
На диаграмме снова изображен конечный автомат из примера 2.1.2.
Определение 2.1.7.
Путь (path) конечного автомата - это кортеж , где
и
для каждого i. При этом q0 - начало пути qn - конец пути n - длина пути w1...wn - метка пути.
Замечание 2.1.8.
Для любого состояния
существует путь . Его метка - , начало и конец совпадают.
Определение 2.1.9.
Путь называется успешным если его начало принадлежит I, а конец принадлежит F.
Пример 2.1.10.
Рассмотрим конечный автомат из примера 2.1.2. Путь
является успешным. Его метка - baaab. Длина этого пути - 4.
Определение 2.1.11.
Слово w допускается (is accepted, is recognized) конечным автоматом M, если оно является меткой некоторого успешного пути.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий