Автоматные модели в программировании

При разработке программ, характеризующейся сложной логикой управления, можно применять автоматный подход, который позволяет сделать текст программы более регулярным и компактным. То же самое решение можно применить, если программа активизируется внешними событиями (событийное программирование) и требуется отследить заданную последовательность наступления событий. В качестве примера, реализованного в виде автоматной модели, рассмотрим функцию, которая исключает из строки комментарии вида “ /* ... */ ”

Прежде всего, необходимо определить состояния автомата, возможные при просмотре очередного символа строки:

• состояние 0 - идет обычный текст;

• состояние 1 - обнаружен символ “/”;

• состояние 2 - обнаружено начало комментария “/*”;

• состояние 3 - в комментарии обнаружен символ “*”.

Программа будет выглядеть следующим образом:

 

void f(char in[],char out[])

{int i, s, j;                                              // s – текущее состояние автомата

for(i=0,s=0,j=0; in[i]!=0; i++)                    // i -  индекс текущего символа входной строки

switch(s)                                               // j – индекс текущего символа выходной строки

      {    

case 0: if (in[i])!=’/’ out[j++] = in[i];           // символы копируются только в состоянии 0

            else s=1;

            break;

case 1: if (in[i]!=’*’)  { out[j++]=in[i-1]; out[j++]=in[i]; s=0; }

            else s=2;

            break;

case 2: if (in[i]==’*’) s=3;

            break;

case 3: if (in[i]==’/’) s=0;

            break;

}}

Подробнее рассмотрим характерные особенности этой программы:

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

• программа имеет переменную s, которая и представляет собой текущее состояние КА. В теле основного цикла программы выполняется переключение (switсh) по всем возможным значениям этой переменной - состояниям КА.

• в каждом состоянии реализуется логика его перехода в другие состояния на основе анализа текущего символа - входного сигнала и вырабатывается соответствующее действие. Например, в состоянии 1, когда программа уже обнаружила символ “/” - возможное начало комментария, она проверяет, не является ли текущий символ “*”. Если это так, автомат переводится в состояние 2 - нахождение внутри комментария, если нет, то в выходную строку переписывается предыдущий “/” и текущий символы, а автомат возвращается в состояние 0.

    Автомат поиска подстрок (построение автомата, поиск подстрок с его помощью)

Автомат для поиска состоит из:

• алфавита  , из символов которого состоят текст и образец;

• множества состояний  ;

• допускающего состояния  ;

• начального состояния  ;

• множества переходов   из одного состояния в другое по символам  .

Переход в   означает, что удалось найти вхождение образца в текст.