yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.1  Конечные автоматы - распознаватели

Дискретная математика

5.1  Конечные автоматы - распознаватели

 

Конечный автомат(в дальнейшем КА) - абстрактное  вычислительное устройство с фиксированным и конечным объемом памяти, которое  на входе читает цепочки(последовательности символов некоторого алфавита), а на выходе сообщает об  их  принадлежности  к  некоторому множеству, для распознания которого он построен.

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

В процессе построения такого конечного автомата должны быть определены следующие параметры:

а) входной алфавит  V  конечного  автомата  (конечное  множество входных символов);

б) конечное множество состояний S;

в) начальное состояние КА - Sнач (состояние, с которого начинает

работу КА при обработке новой цепочки);

г) множество допускающих состояний  -  Sдоп  (подмножество  множества состояний S, с которым сравнивается  достигнутое  КА  состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре текущее состояние - входной символ ставит в соответствие новое состояние).

Примечания:

1.В множество входных символов V  обязательно  включают  особый символ "конец цепочки", который сообщает КА о том, что нужно достигнутое состояние сравнить с множеством Sдоп и, если оно приналежит этому множеству, пропустить цепочку; в противном случае цепочка отвергается. В тексте этот символ будет иметь вид -+.

2.Часто при распознании цепочек возникает ситуация,  когда  невозможно поставить текущей паре  состояние-входной  символ  новое состояние.  По сути это означает, что распознаваемая  цепочка  не принадлежит распознаваемому множеству, хотя она и не  просмотрена до символа "конец цепочки".  Такие ситуации в  таблице  переходов помечаются символом "Е" ("error"); попав в такое состояние КА отвергает текущую цепочку и  переходит  в  начальное  состояние.  В конкретных программных реализациях  может  вызываться  обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.

Начинает работать КА из начального состояния. Символы распознаваемой цепочки поступают посимвольно, начиная с первого  и  изменяют состояния в соответствии с таблицей переходов. После поступления символа "конец  цепочки",  достигнутое  состояние  автомата фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается. По сути КА работает как фильтр, который пропускает "правильные"  цепочки.  Другая трактовка КА - компактный алгоритм распознания регулярных, в том числе  и  бесконечных  множеств,  который  строит программист перед началом кодирования (реализацией  алгоритма  на конкретном языке).

Построение КА для распознания  заданного  множества  цепочек  - процесс творческий и неоднозначный.  Теоретически для распознания одного и того же множества цепочек  можно  построить  бесконечное множество КА.  Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству.

 

 

27