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

Конечный автомат-распознаватель (finite automaton, finite-state machine) – это пятёрка конечных множеств a_R=(A, Q, D, I, F),где A – входной алфавит данного автомата, Q – множество состояний автомата, , – множество начальных состояний (initial states), –множество заключительных или допускающих (final, accepting) состояний. Если <p,x,q>ÎD, то <p,x,q> называется переходом (transition) из р в q, а слово х — меткой (label) этого перехода.

Конечные автоматы-распознаватели можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)) – это аналог диаграмм Мура для конечных автоматов-преобразователей.

Определение 2.1.1. Диаграмма переходов для конечного автомата-распознавателя – это ориентированный многокорневой псевдограф

(а) множество вершин которого совпадает с множеством Q, причем каждое начальное состояние распознаётся по ведущей в него короткой стрелке, а каждое допускающее состояние отмечается на диаграмме двойным кружком;

(б) его дуги из р в q (pÎQ, qÎQ) помечаются словом хÎА* и, таким образом, они соответствуют переходам <p,x,q> данного автомата.

Пример 2.1.2.Пусть A={a, b}, Q={1, 2}, I={1}, F ={2}, D={<1,ааа,1>, <1,аb,2>, <1,b,2>, <2,e,1>}. Тогда a_R=(A, Q, D, I, F)– конечный автомат-распознаватель. Его диаграмма переходов имеет вид:

Замечание 2.1.3.Если в автомате-распознавателе имеются несколько переходов с общим началом и общим концом, то такие переходы называются параллельными. На диаграмме состояний они соответствуют кратным ребрам и поэтому их иногда изображают одной дугой. При этом метки переходов перечисляют через запятую.

Пример 2.1.4.На диаграмме снова изображён конечный автомат из примера 2.1.2.

Определение 2.1.5.Конфигурацией или мгновенным описанием (instantaneous description) конечного автомата a_R=(A, Q, D, I, F)называется любая упорядоченная пара (q, w),где qÎQ и wÎA*.

Замечание 2.1.6.Содержательно конфигурация представляет собой «мгновенное описание» конечного автомата. Если представить, что исходное слово, принадлежность которого рассматриваемому языку надо проверить, дано в некотором «входном потоке», то в конфигурации (q, w)слово w есть та часть исходного слова, которая пока осталась во входном потоке (это некоторый суффикс исходного слова), a q –текущее состояние «управляющего устройства» (см. п. 2.2).

Определение 2.1.7.Путь (path) конечного автомата – это кортеж ,где и для каждого i. При этом q₀– начало пути, q_n – конец пути, п – длина пути,w₁ ,…,w_n – метки пути.

Замечание 2.1.8.Для любого состояния qÎQ существует путь <q>. Его метка – e, начало и конец совпадают.

Определение 2.1.9.Путь называется успешным, если его начало принадлежит I, а конец – F.

Определение 2.1.11.Слово w допускается (is accepted, is recognized) конечным автоматом a_R , если оно является меткой некоторого успешного пути.

Пример 2.1.10.Рассмотрим конечный автомат из примера 2.1.2. Путь <1, <1, b, 2>, 2, <2, e, 1>, 1, <1, aaa, l>,1, <1, b, 2>, 2) с краткой записью <1, b, 2, e, 1, aaa, 1, b, 2> является успешным. Его длина равна 4, а метка – baaab. Значит, слово baaab допускается данным автоматом.

Определение 2.1.12.Язык, распознаваемый конечным автоматом a_R, – это язык L(a_R), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат a_R распознаёт (recognizes, accepts) язык L(a_R).

Определение 2.1.15.Два конечных автомата эквивалентны, если они распознают один и тот же язык.

Замечание 2.1.13.Если , то язык L(a_R), где a_R=(A, Q, D, I, F),содержит e.

Пример 2.1.14.Пусть a_R=(A, Q, D, I, F), где A={a, b}, Q={1, 2}, I={1}, F={1, 2}, D={<1,а,2>, <2,b,1>}.

Тогда L(a_R)= .

Определение 2.1.16.Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.

Замечание 2.1.19.Каждый конечный язык является автоматным, а бесконечный язык может быть как автоматным, так и не автоматным.

Пример 2.1.18.Рассмотрим однобуквенный алфавит А={а}. При любых фиксированных и язык является автоматным. Например, при автомат выглядит так:

Определение 2.1.20.Состояние q достижимо (reachable) из состояния р, если существует путь, началом которого является р, а концом — q.

Лемма 2.1.21.Каждый автоматный язык распознаётся некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.

Пример 2.1.22.Рассмотрим конечный автомат a_R=(A, Q, D, I, F), где A={a, b, c, d}, Q={1, 2, 3, 4}, I={1, 2, 4}, F={1, 3, 4}, D={<1,а,2>, <1,b,4>, <3,c,4>, <4,d,1>}.

Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требованиям леммы 2.1.21. Получается эквивалентный конечный автомат (A, Q’, D’, I’, F’), где Q’={1, 4}, I’={1, 4}, F’={1, 4}, D’={<1,b,4>, <4,d,1>}.