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

После рассмотрения автоматов-преобразователей перейдем к изучению второго распространенного типа конечных автоматов – автоматов-распознавателей. От автоматов-преобразователей они отличаются тем, что функции выходов и переходов не зависят от входных сигналов и являются одноместными функциями состояний.

В общем случае автомат-распознаватель не даёт точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Поэтому не все конечные автоматы-распознаватели подходят для конструирования распознающих устройств, пригодных для практических приложений. Этого недостатка нет у детерминированныхавтоматов (частного случаянедетерминированныхавтоматов).

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

Конечный автомат-распознаватель (finite automaton, finite-state machine) – это пятёрка конечных множеств _R=(A, Q, , I, F), где A – входной алфавит данного автомата, Q – множество состояний автомата, , – множество начальных состояний (initial states), – множество заключительных или допускающих (final, accepting) состояний. Если <p,x,q>, то <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}, ={<1,ааа,1>, <1,аb,2>, <1,b,2>, <2,,1>}. Тогда _R=(A, Q, , I, F) – конечный автомат-распознаватель. Его диаграмма переходов имеет вид:

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

П

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

Определение 2.1.5. Конфигурацией или мгновенным описанием (instantaneous description) конечного автомата _R=(A, Q, , 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>. Его метка – , начало и конец совпадают.

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

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

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

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

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

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

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

Тогда L(_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. Рассмотрим конечный автомат _R=(A, Q, , I, F), где A={a, b, c, d}, Q={1, 2, 3, 4}, I={1, 2, 4}, F={1, 3, 4}, ={<1,а,2>, <1,b,4>, <3,c,4>, <4,d,1>}.

У

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