Формальной основой ЛА являются конечные автоматы (КА). КА является формальным математическим аппаратом, широко используемым в компьютерной технике. В проектировании аппаратных средств КА используются при разработке управляющей схемы, реализующей заданный алгоритм. Точно так же, в любой программе достаточно сложная логика последовательности действий может быть реализована как напрямую в виде последовательности условных и циклических конструкций, так и в виде программного КА. Для начала дадим неформальное определение КА.
КОНЕЧНЫМ АВТОМАТОМ является система, которая в каждый момент времени может находится в одном из конечного множества заданных состояний. Каждый шаг (переключение) автомата состоит в том, что при нахождении в определенном состоянии при поступлении на вход одного из множества входных сигналов (воздействий) он переходит в однозначно определенное состояние и вырабатывает определенное выходное воздействие. Легче всего представить себе поведение КА в виде его диаграммы состояний-переходов.
Таким образом, если поведение какого-либо объекта можно описать набором предложений вида: находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D - то такая система будет представлять из себя конечный автомат. На диаграмме состояний-переходов каждому состоянию соответствует кружок, каждому переходу - дуга со стрелкой. Каждое состояние имеет свой “смысл”, заключенный в подписи. Каждый переход осуществляется только при выполнении определенного условия, которое обозначено подписью под дугой. Кроме того, при выполнении перехода производится действие, при помощи которого автомат обнаруживает свое поведение извне.
У конечного автомата есть еще несколько условий работоспособности:
- автомат имеет некоторое начальное состояние, из которого он начинает работу;
- автомат имеет конечное число состояний;
в каждом состоянии не может быть одновременно справедливыми несколько условий перехода, то есть автомат должен быть ДЕТЕРМИНИРОВАННЫМ.
Автомат не может перейти одновременно в несколько состояний и не может иметь таких условий перехода.
О том, что конечный автомат может использоваться при анализе последовательностей различных символов в строке, несложно убедиться на простом примере. Пусть требуется написать программу, которая исключает из строки комментарии вида “ /* ... */ ”
Прежде всего, необходимо определить состояния конечного автомата. Таковыми являются состояния программы, возможные при просмотре очередного символа строки:
- состояние 0 - идет обычный текст;
- состояние 1 - обнаружен символ “/”;
- состояние 2 - обнаружено начало комментария “/*”;
- состояние 3 - в комментарии обнаружен символ “*”.
Программа, представляющая собой КА, будет выглядеть следующим образом:
void f(char in[],char out[])
{int i, s, j;
for(i=0,s=0,j=0; in[i]!=0; i++)