2015-06-28
3020
Конечный автомат (в дальнейшем КА) – абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки (последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.
Принцип работы конечных автоматов различных уровней широко применяется в вычислительных устройствах как на аппаратном, так и на программном уровнях: это компиляторы, трансляторы программ, различные кодировщики, антивирусные программы и т.п. В принципе работу любой программы можно представить как работу цепочки конечных автоматов различной сложности. Рассмотрим построение простейших КА – распознавателей. В процессе построения такого конечного автомата должны быть определены следующие параметры:
а) входной алфавит V конечного автомата (конечное множество входных символов, которые будет распознавать КА);
б) конечное множество состояний S;
в) начальное состояние КА – s 0 (состояние, с которого начинает работу КА при обработке новой цепочки);
г) множество допускающих состояний – S доп (подмножество состояний, с элементами которого сравнивается достигнутое КА состояние после прихода символа "конец цепочки");
д) таблица переходов (управляющая таблица), которая паре "текущее состояние – входной символ" ставит в соответствие новое состояние КА из множества состояний S).
Примечания:
1 В множество входных символов обязательно включают особый символ "конец цепочки", который сообщает КА о том, что достигнутое состояние si нужно сравнить с элементами множества S доп и, если si Î S доп , пропустить цепочку; в противном случае цепочка отвергается. В тексте этот символ будет иметь вид –|.
2 Часто при распознании цепочек возникает ситуация, когда невозможно текущей паре "состояние – входной символ" поставить в соответствие новое состояние. По сути это означает, что цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом " Е " ("error"); попав в такое состояние, КА отвергает проверяемую цепочку и переходит в начальное состояние. В конкретных программных реализациях может вызываться обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.
КА всегда начинает работу из начального состояния s 0. Символы распознаваемой цепочки поступают посимвольно, начиная с первого, и изменяют состояния КА в соответствии с таблицей переходов. После поступления символа "конец цепочки" достигнутое автоматом состояние фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается. По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА – компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке программирования).
Построение КА для распознания заданного множества цепочек – процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству. Он эффективен в следующих случаях:
– распознаваемые цепочки содержат определенные сочетания символов в начале, конце или (и) середине цепочки;
– распознаваемые цепочки содержат ограниченное число повторений определенных символов или их сочетаний (не больше n; точно n; не меньше n, причем n = 1,2,3);
– распознаваемые цепочки содержат запрет на определенные сочетания символов в начале, конце или (и) во всей цепочке;
– распознаваемые цепочки содержат комбинации названных выше ограничений. (более подробно – см. лекции по ДМ).
