Математическая теория формальных языков
Недетерминированные конечные автоматы
Определение 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, если оно является меткой некоторого успешного пути.
Определение 2.1.12.
Язык, распознаваемый конечным автоматом M, - это язык L(M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает (recognizes, accepts) язык L(M).
Замечание 2.1.13.
Если , то язык, распознаваемый конечным автоматом , содержит .
Пример 2.1.14.
Пусть , где Q = {1,2}, , I = {1}, F = {1,2},
Тогда
Определение 2.1.15.
Два конечных автомата эквивалентны, если они распознают один и тот же язык.
Определение 2.1.16.
Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.
Замечание 2.1.17.
Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).
Пример 2.1.18.
Рассмотрим однобуквенный алфавит . При любых фиксированных
и
язык
является автоматным.
Замечание 2.1.19.
Каждый конечный язык является автоматным.
Определение 2.1.20.
Состояние q достижимо (reachable) из состояния p, если существует путь, началом которого является p, а концом - q.
Лемма 2.1.21.
Каждый автоматный язык распознается некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.
Пример 2.1.22.
Рассмотрим конечный автомат , где Q = {1,2,3,4}, , I = {1,2,4}, F = {1,3,4},
Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требованиям леммы 2.1.21. Получается эквивалентный конечный автомат , где Q' = {1,4}, I' = {1,4}, F' = {1,4},
Замечание 2.1.23
Естественным обобщением конечного автомата является конечный преобразователь (finite-state transducer), позволяющий на каждом такте отправить несколько символов в дополнительный "выходной" поток. В некоторых книгах конечными автоматами называют именно такие устройства (с выходным потоком).
В данном пособии конечные преобразователи рассматриваться не будут.
Упражнение 2.1.24. Найти конечный автомат, распознающий язык
Упражнение 2.1.25. Найти конечный автомат, распознающий язык
Упражнение 2.1.26. Найти конечный автомат, распознающий язык
Упражнение 2.1.27. Найти конечный автомат, распознающий язык
Упражнение 2.1.28. Найти конечный автомат, распознающий язык
Упражнение 2.1.28. Найти конечный автомат, распознающий язык , где ,
и
для любого
