8.8. АВТОМАТЫ КАК РАСПОЗНАЮЩИЕ УСТРОЙСТВА

Грамматики, изученные в предыдущих разделах, были в основном схемами, порождающими цепочки. В этом параграфе мы кратко коснемся теории автоматов и введем понятие автомата как системы распознавания цепочек. Связь между этой теорией и распознаванием образов очевидна, поскольку, как это было показано в предыдущих разделах, образы часто можно выразить в виде терминальных цепочек. Хотя исчерпывающий анализ автоматов лежит за пределами нашего обсуждения, мы рассмотрим несколько подробнее один специфический тип автоматов — конечные автоматы — и покажем, что конечный автомат способен распознавать автоматные языки (языки типа 3).

Конечный автомат над алфавитом 2 определяется как пятерка

где К — конечное непустое множество состояний, — конечный входной алфавит, — отображение — начальное состояние и — множество заключительных состояний. Терминология и система обозначений иллюстрируются следующим примером.

Пример. Рассмотрим автомат, заданный набором (8.8.1), где

и — отображение в К — задается таким образом:

Если, например, автомат находится в состоянии и на вход поступает символ , то автомат переходит в состояние . Если далее на вход поступает символ 1, то автомат переходит в состояние . Заметим, что в данном случае заключительное состояние равно начальному состоянию.

Диаграмма состояний этого автомата, приведенная на рис. 8.12, состоит из вершин, соответствующих каждому из возможных состояний, и ориентированных ребер, соединяющих взаимно достижимые состояния. В данном примере, если состояние было бы недостижимо из состояния и обратно, на диаграмме не существовало бы ребра между этими двумя состояниями. Каждое ребро диаграммы обозначается соответствующим символом из множества 2, обусловливающим переход автомата в указанное состояние.

Рис. 8.12. Конечный автомат.

Предположим, что автомат находится в состоянии и на вход подается цепочка Автомат просматривает цепочку слева направо по одному символу за такт. Встретив первый , автомат переходит в состояние Следующий заставляет его вернуться в состояние Точно так же следующий символ, которым является 1, меняет состояние автомата на а вторая 1 возвращает его в исходное состояние Завершение этой процедуры не требует разъяснений. Совершенно очевидно., что после прочтения цепочки автомат будет находиться в состоянии

Если в результате просмотра цепочки или предложения автомат находится в одном из возможных заключительных состояний,

то говорят, что цепочка допускается автоматом Множество всех цепочек допускаемых автоматом обозначается , т. е.

где обозначает состояние автомата после прочтения цепочки

Если цепочками представлены образы, то нам удобно рассматривать конечный автомат как устройство, обеспечивающее разделение на два класса: цепочка приписывается к классу если она допускается, и к классу если она не допускается автоматом.

Можно показать, что если задана автоматная грамматика , то существует конечный автомат такой, что . И обратно, если задан конечный автомат то существует автоматная грамматика такая, что .

Исследования в теории автоматов показывают, что неограниченная грамматика, грамматика непосредственно составляющих и бесконтекстная грамматика могут распознаваться другими типами автоматов. Неограниченные языки допускаются машинами Тьюринга; языки непосредственно составляющих — линейно ограниченными автоматами; бесконтекстные языки — магазинными автоматами. Кроме того, теория автоматов легко допускает статистические постановки, как показано в работе Фу [1970]. Стохастические автоматы могут использоваться для распознавания стохастических языков. Можно также задать такой автомат, который будет допускать не цепочечные, а древовидные структуры. Читателю, заинтересованному в углублении своих познаний по этому вопросу, можно порекомендовать, например, работы Фу и Бхаргавы [1973], Тэтчера [1973], Гонсалеса и Томасона [1974а].