Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

10.2. ПОДСЧЕТ ДЛИН СЛОВ

565

и по этой причине их исключение нежелательно, поскольку приводит к неяс-

ности программы. Но если подобных оснований нет, то следует постараться

объединить действия, связанные с нестандартным переходом и с последую-

щими переходами, чтобы исключить переходы без чтения.

Из перечня действий для рассматриваемой задачи следует, что должно

быть, как минимум, два класса состояний, имеющие разные действия-реак-

ции.

Следующий методический прием — это определение начального состо-

яния, т. е. того, в котором вычислительный процесс активизируется. Нужно

указать, какие действия возможны в данном состоянии, и какие условия пе-

рехода в нем должны быть.

Для рассматриваемого случая в начальном состоянии (

St1

), возможны

действия:

1 с переходом в другое состояние —

St2

(поскольку следующая буква

требует другой реакции),

4 с сохранением состояния и

6 завершение обработки.

Инициализировать

обработку слова

Символ конец

строки

Символ не буква

Символ

буква

St1

Вход

Выход

St2

Завершить процесс

Рис. 10.2. Начало построения графа состояний

Результат только что проведенного анализа можно представить в виде гра-

фа, изображенного на рис. 10.2. С каждой дугой графа связано две пометки:

566

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

символ-условие перехода и ассоциированное действие. Вход и выход обозна-

чаются черными прямоугольными блоками. При желании их можно считать

специальными состояниями, с которыми ассоциированы действия инициа-

лизации и завершения процесса. Состояние

St2

изображено штриховой ли-

нией, поскольку анализ его еще не проведен.

Таким образом появляются новые состояния (в примере —

St2

). Для ка-

ждого из них следует определить условия перехода и соответствующие им

действия.

В рассматриваем случае в состоянии

St2

возможны действия:

2 с сохранением состояния,

3 с переходом в другое состояние, которому дается временное имя

St3

5 окончание слова и всего потока, завершение обработки.

После этого построения проверяется, не является новое состояние копией

уже имеющегося как по действиям, так и по переходам. Если это так, то но-

вое состояние можно отождествить (склеить) с одним из ранее построенных.

Вновь появляющиеся состояния анализируются аналогично.

Для решаемой задачи легко выяснить, что состояние

St3

требует тех же

действий и переходов, что и

St1

. Следовательно, возможна склейка этих двух

состояний и построение графа завершается, так как новых состояний нет

(см. рис. 10.3). При желании, чтобы не дублировать действия “Завершить

процесс” можно еще определить еще одно, заключительное состояние, с вы-

ходом из которого будет ассоциировано это действие (один раз!). Понятно,

что это состояние будет иметь нестандартный переход.

Представленный метод выявления состояний конечного автомата годится

для не очень больших задач, когда строящийся граф остается обозримым. Он

может быть улучшен, если в ходе анализа задачи заранее удается выявить со-

держательно обособленные состояния и переходы между ними. Так,для дан-

ной задачи вполне очевидно, что обрабатывающая программа должна рабо-

тать по-разному,когда слово еще не началось, и когда уже прочитаны его пер-

вые символы. Иными словами, вычислительный процесс может находиться

в двух состояниях: ожидание начала слова (

St1

) и ожидание окончания слова

(

St2

). Для каждого из них можно указать набор действий, ассоциированных

с переходами, которые явно зависят от содержательного смысла состояний.

Содержательное выделение состояний удобно. В частности, можно себе

позволить строить недетерминированный конечный автомат, т. е. такой, у ко-

торого есть состояния с разными переходами, определяемыми одним и тем

10.2. ПОДСЧЕТ ДЛИН СЛОВ

567

Выход

Вход

Символ конец

строки

Символ конец

строки

Завершить процесс

Закончить обработку слова

Символ не буква

Продолжить

обработку слова

Символ

буква

Инициализировать

обработку слова

Символ не буква

Символ

буква

St1

St2

Завершить процесс

Рис. 10.3. Полученный граф состояний

же условием. Абстрактная точка зрения на такую ситуацию состоит в том,

что при вычислениях выбирается любой из переходов.

Недетерминирован-

ный конечный автомат может быть автоматически преобразован в детерми-

нированный, при этом появляются новые состояния, которые не влияют на

логическое представление алгоритма.

10.2.3. Табличное представление графа состояний конечного автома-

та

Графическое или иное представление графа состояний конечного авто-

мата, явно отражающее наименования состояний, условия переходов между

состояниями и ассоциированные с ними действия, называют диаграммой пе-

реходов. Это определение подчеркивает характерные особенности алгорит-

мической природы конечного автомата, вычисления которого сводятся к ал-

Возможен и такой вариант, когда выбирается тот переход, который ведет к цели. Но это

означает, что осуществляется перебор вариантов, причем, возможно, на большую глубину,

поскольку часто после выполнения одного перехода неясно, продвинулись ли мы к цели, и

нужно дойти до явно тупиковой ситуации. Практически здесь возникает одна из форм сен-

тенциального программирования, и представление ее недетерминированной таблицей со-

стояний и переходов скорее случайная теоретическая аналогия, сбивающая с толку на прак-

тике.

568

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

горитму перемещения по графу состояний от одного состояния к другому с

выполнением ассоциированных действий.

Различают визуальные представления диаграмм переходов,которые пред-

назначены для человека, и их программные представления, которые предна-

значены для выполнения программ конечных автоматов. Требования к визу-

альным представлениям — понятность для человека, статическая проверя-

емость свойств; требования к программным представлениям — осуществи-

мость эффективной обработки, заданной конечными автоматами; общее тре-

бование к представлениям обоих видов — однозначное соответствие меж-

ду ними, позволяющее утверждать пошаговую вычислительную эквивалент-

ность.

Какое представление графа состояний лучше всего использовать?Как все-

гда, ответ на этот вопрос зависит от сложности графа, статичности либо ди-

намичности его и того, для каких целей требуется спецификация в виде графа

состояний. Понятно, что важнейшей для нас промежуточной целью является

программа на алгоритмическом языке. Но подходы к построению такой про-

граммы могут быть различными. Существует две принципиально различные

позиции:

• трансляционная —структура управления программы определяется гра-

фом состояний;

• интерпретационная — строится специальная программа, которая вос-

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

Как при трансляционной, так и интерпретационной позиции возможен це-

лый спектр реализаций, некоторые из которых будут приведены ниже. Бли-

жайшая же цель в том, чтобы научиться удобно представлять граф конечного

автомата для человека. Наиболее естественно описывать его в виде таблицы

(см. таблицу 10.1) со следующими полями-колонками:

1. Наименование состояния — входы в таблицу;

2. Условие (срабатывания) перехода — логическое выражение или слу-

жебное слово

failure

,которое указывает на действие, выполняемое, если

ни одно из условий не срабатывает;

3. Действие, ассоциированное с переходом — последовательность опера-

торов, выполняемая, когда условие перехода истинно;

4. Адрес перехода — наименование состояния-преемника.

10.2. ПОДСЧЕТ ДЛИН СЛОВ

569

char symbol; //

Как ранее, чтение потока символов неявное

int cnt; ...//

Инициализация

St1

St1 ’a’<=symbol &&

symbol <=

’z’

printf ("%c", symbol); cnt =

1; St2

/*(symbol<’a’

’z’<Symbol) &&*/

symbol!=’\n’

Так как нужно печатать только сло-

ва, действия не заполняются

St1

ailure //

Переход не требует чтения

// symbol == ’\n’

не нужно читать

exit

St2 ’a’<=symbol &&

symbol <=

’z’

printf ("%c",

symbol);cnt++; St2

/*(symbol<’a’

’z’<symbol) &&*/

symbol !=

’\n’

printf ("- %i\n",

Cnt); St1

ailure printf ("- %i\n", Cnt); exit

xit /*

отсутствие

условия — ис-

тина, но без

неявного чтения

потока

return 0; //

Считать данную секцию та-

блицы

состоянием или нет — дело вкуса

Таблица 10.1. Табличное представление графа состояний

570

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

Кроме того, определяется специальная (первая) строка, в которой поме-

щаются операторы, инициирующие процесс, и адрес перехода начального

состояния.

Таблица 10.1 есть просто более формализованное представление рисунка

10.3. При желании табличное представление можно рассматривать как свое-

образный язык программирования, для которого может быть построен транс-

лятор или интерпретатор в точном соответствии с обозначенными выше по-

зициями по отношению к конечной цели решения задачи, т. е. к реализации

программы на алгоритмическом языке. Семантика вычислений на этом язы-

ке понятна. Рассматривается контекст некоторой программы на языке

С/C++

(или на другом языке традиционного типа), в этом контексте определяется

значение переменной

Entry

(все множество ее значений совпадает с множе-

ством наименований состояний) и выполняется следующее:

Выбрать

вход в таблицу, соответствующий значению

Entry

(текущее

состояние).

Если Условие

отсутствует,

то перейти к

шагу 4.

Вычислить совместно

все

Условия

срабатывания переходов (клетки

второй колонки для данного входа):

(a) Если среди результатов есть значения

True

то выбрать

одну из

строк,

Условие

которой истинно, и

перейти к

шагу 4 для выбран-

ной строки

;

(b)

Если

все значения

Условий

ложны и есть строка

failure

то вы-

брать

эту строку и перейти к шагу 4 для нее;

(c)

Если

все значения

Условий

ложны

нет строки

failure

то завер-

шить

вычисления автомата.

Выполнить Действие

5. В качестве значения переменной

Entry

установить наименование со-

стояния-преемника (из четвертой колонки таблицы).

Перейти к

шагу

В этом пункте может быть заложено недетерминированное поведение автомата. Очень

часто при применении метода конечных автоматов возможность недетерминированного по-

ведения игнорируется: оно исключается путем задания последовательных проверок и выбо-

ра первого из действий, для которого значение условия есть

True

. Это очень похоже на то,

как определены условные выражения и оператор переключения в языке

С/С++

10.2. ПОДСЧЕТ ДЛИН СЛОВ

571

Для данного примера указанной семантики вычислений достаточно (обра-

тите внимание на то, что для завершения процесса используется оператор

return 0;

). В некоторых случаях может оказаться полезным расширение вы-

разительных возможностей таблиц за счет добавления факультативных дей-

ствий, ассоциированных с состоянием, которые выполняются в самом нача-

ле и в самом конце обработки текущего состояния. Этого можно достичь,

например, с помощью специальных служебных слов:

•

start

— указание действий, которые выполняются до основных дей-

ствий и проверок условий перехода (может использоваться в качестве

первой графы таблицы),

•

ﬁnish

— указание действий, которые выполняются после основных

действий и проверок, но до перехода (может использоваться в качестве

последней графы таблицы);

Можно также определять локальные для состояний данные (в примере такие

данные определены только для начального состояния), но это должно быть

согласовано с правилами локализации имен языка программирования и с об-

щим стилем,в котором написана программа. Заметим, что локальные данные

всех состояний конечного автомата должны быть помещены в общий кон-

текст, а приписывание их к конкретным состояниям является ограничением

видимости, подобным тому, о котором говорилось при рассмотрении моду-

лей в § 12.2 (еще раз прослеживается аналогия между модулями и состояни-

ями!). Это прагматически следует из того положения, что работа конечного

автомата не требует привлечения памяти.

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

описания различных типов автоматных алгоритмов. А пока займемся реше-

нием вопроса о том, как запрограммировать требуемые действия, когда нет

возможности воспользоваться таблицей непосредственно. Вот что можно де-

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

1. Оттранслировать вручную;

2. Отдать препроцессору для превращения в нормальную программу;

3. Использовать интерпретатор.

Рассмотрим последовательно эти три возможности.

572

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

10.2.4. Ручная трансляция диаграмм переходов

Решения 1 и 2 ставят следующий вопрос: во что транслировать таблицу

переходов?Вариантов может быть очень много.Ниже рассматриваются лишь

некоторые из них.

Вариант 1: считать

St1

St2

функциями, реализующими все действия

состояний.

Программа 10.2.1 Длины слов: рекурсия

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

char symbol; //

Переменная для чтения потока

int cnt; //

Переменная для счета длин слов (из анализа

возможных решений задачи)

void St2 (); //

Предописание функции

void St1 ()

{

if (’a’<= symbol && symbol <= ’z’)

{

printf ("%c", symbol);

cnt = 1;

symbol = getchar ();

St2 ();

}

else if ( symbol != ’\n’ )

{

symbol = getchar ();

St1 ();

}

void St2 ()

{ if (’a’<= symbol && symbol <= ’z’)

{

printf ("%c",symbol);

10.2. ПОДСЧЕТ ДЛИН СЛОВ

573

cnt += 1;

symbol = getchar ();

St2 ();

}

else if ( symbol != ’\n’ )

{

printf (" - %i\n", cnt);

symbol = getchar ();

St1 ();

}

else printf (" - %i\n", cnt);

}

void main( void )

{

symbol = getchar ();

St1 ();

}

Это плохая программа, в частности, по той причине, что рекурсия есть фак-

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

для конечного автомата динамического расходования памяти не требуется.

Одна из возможных причин появления такой программы в том,что факти-

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

задана неявно. Попробуем сделать ее явной, соответствующей предположе-

ниям о виде потоковой обработки, сделанным в § 7.2.

Вариант 2: считать

St1

St2

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

State

Программа 10.2.2 Длины слов: явный цикл обработки потока

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

char symbol;

int cnt;

enum States { St1, St2 } State;

void main( void )

574

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

{

State = St1;

while ( (symbol = getchar ()) != ’n’)

switch ( State )

{ case St1: if (’a’<=symbol && symbol <= ’z’)

{ printf ("%c", symbol);

cnt = 1;

State = St2;

}

else // if (symbol != ’\n’)

// State = St1;

// else if (symbol == ’\n’) return;

break;

case St2: if (’a’<=symbol && symbol <= ’z’)

{ printf ("%c", symbol);

cnt++; // State = St2;

}

else if (symbol != ’\n’)

{ printf (" - %i\n", cnt);

State = St1;

}

else

{ printf (" - %i\n", cnt);

return;

}

Лучше ли программа 10.2.2? Да, но только если ограничиться представлен-

ным выше критерием. Программа точно соответствует табличному предста-

влению автомата, почти все дублирования действий, связанные с таким пред-

ставлением, ликвидированы. Однако остается неудовлетворенность тем, что

появилось лишнее действие: выбор выполняемого фрагмента по значению

переменной

State

Если ограничиться управляющими средствами методологии структурно-

го программирования, то это — непреодолимое препятствие. Попытки при-

менить циклы внутри фрагментов, помеченных как

case St1:

case St2:

при-

водят лишь к уменьшению наглядности по сравнению с табличным предста-