Табличное представление графа состояний
Графическое или иное представление графа состояний конечного автомата, явно отражающее наименования состояний, условия переходов между состояниями и ассоциированные с ними действия, называют таблицей переходов. Такое представление является одним из центральных компонентов широко используемого в индустриальном программировании языка объектно-ориентированного дизайна UML (в частности, в форме, реализованной в системе Rational Rose) - state transition diagrams (диаграммы состояний и переходов).
Различают визуальные представления таблиц переходов, которые предназначены для человека, и их программные представления. Требования к визуальным представлениям - понятность для человека, статическая проверяемость свойств; требования к программным представлениям - выполнимость при посредстве какой-либо системы программирования; общее требование к представлениям обоих видов - однозначное соответствие между ними, позволяющее обоснованно утверждать вычислительную эквивалентность.
Ответ на вопрос, какое представление графа состояний лучше всего использовать, зависит от сложности графа, статичности либо динамичности его и того, для каких целей требуется спецификация в виде графа состояний. Понятно, что важнейшей для нас промежуточной целью является программа на алгоритмическом языке. Но подходы к построению такой программы могут быть различны. Существует две принципиально различные методики применения спецификаций:
- трансляционная - генерируется программа, структура управления которой определяется графом состояний;
- интерпретационная - строится специальная программа, которая воспринимает некое представление графа как задание для интерпретации.
Как при трансляционной, так и интерпретационной позиции возможен целый спектр реализаций. Ближайшая же цель в том, чтобы научиться удобно для человека представлять граф состояний и переходов. Наиболее естественно описывать его в виде таблицы. Для методов на переходах и в состояниях таблицы несколько различаются. На табл. 9.1 представлен случай Мили.
Опишем значение колонок таблицы.
- Наименование состояния - входы в таблицу.
- Условие (срабатывания) перехода - логическое выражение или служебное слово failure, которое указывает на действие, выполняемое, если ни одно из условий не срабатывает.
- Действие, ассоциированное с переходом, - последовательность операторов, выполняемая, когда условие перехода истинно.
- Адрес перехода - наименование состояния-преемника.
Кроме того, определяется специальная (первая) строка, в которой помещаются операторы, инициирующие процесс, и адрес перехода начального состояния.
В табличном представлении графа переходов в состояниях (таблица 9.2) действия помещаются во втором столбце, сразу после обозначения состояния, а уже затем идут переходы. Анализируя таблицу 9.2, можно заметить ряд повторяющихся действий. Конечно же, если бы эти действия были более сложными, их просто описали бы как процедуры. Но такие повторения заставляют задуматься, а нельзя ли сократить число состояний? Введя дополнительную булевскую переменную, отметившую, что последним символом был перевод строки, мы могли бы избавиться от пары состояний. Но такой переменной нужно присваивать новое значение в процессе проверки условий, и при этом в строго определенный момент: сначала проверить, не является ли символ концом строки, а уже затем переприсваивать данную переменную. Это решение сильно отдает хакерством, и, если Вы хотите писать качественные, легко перестраиваемые программы, то таких решений нужно избегать.
Еще раз показать тонкую грань между хакерством и естественностью можно, рассмотрев один из моментов, возникающих в наших программах. При работе в состояниях нам приходится обнулять счетчик букв слова в тот момент, когда кончается очередное слово, поскольку иначе пришлось бы выделять еще одно состояние, соответствующее середине обработки слова. Но это гораздо менее искусственное решение: неплохо восстанавливать начальные значения и делать другие действия по приведению в порядок информации в тот момент, когда заканчивается очередной этап работы; неплохо делать это всегда в начале нового этапа; плохо лишь произвольно перемешивать эти две дисциплины.
|
char symbol; // Чтение потока символов неявное // Чтение происходит перед выполнением проверок и действий int Cnt; . . . // Инициализация | St1|
| 'a'<=symbol && symbol <= 'z' | printf ("%c", symbol); Cnt = 1; | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol!='\n' | /* Действий нет */ | St1
| symbol='\n' | /* Действий нет */ | St3
| 'a'<=symbol && symbol <= 'z' | printf ("%c", symbol);cnt++; | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n' | printf ("- %i\n", Cnt); | St1
| symbol='\n' | printf ("- %i\n", Cnt); | St3
| 'a'<=symbol && symbol <= 'z' | printf ("%c", symbol); Cnt = 1; | St2
| /*(symbol<'a'|| 'z'<Symbol) &&*/ symbol!='\n' | /* Действий нет */ | St1
| symbol='\n' | Второй '\n' дальше не нужно читать | exit
| /* Нет неявного чтения потока */ | return 0; // Считать данную секцию таблицы состоянием или нет - дело вкуса |
|
char symbol; // Чтение потока символов неявное // Чтение происходит после выполнения действия, перед проверками int Cnt; ...Cnt=0; // Инициализация | St1|
| /* Действий нет */ | 'a'<=symbol && symbol <= 'z' | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol!='\n' | St1|
| symbol='\n' | St3|
| printf ("%c", symbol); Cnt++; | 'a'<=symbol && symbol <= 'z' | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n' | St4|
| symbol='\n' | St5|
| /* Действий нет */ | 'a'<=symbol && symbol <= 'z' | St2
| /*(symbol<'a'|| 'z'<Symbol) &&*/ symbol!='\n' | St1|
| Второй '\n' дальше не нужно читать symbol='\n' | exit|
| printf ("- %i\n", Cnt); Cnt=0; | 'a'<=symbol && symbol <= 'z' | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n' | St1|
| symbol='\n' | St3|
| printf ("- %i\n", Cnt); Cnt=0; | 'a'<=symbol && symbol <= 'z' | St2
| /*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n' | exit|
| Второй '\n' дальше не нужно читать symbol='\n' | exit|
| /* Нет неявного чтения потока */ | return 0; // Считать данную секцию таблицы состоянием или нет - дело вкуса |
 |
|
|
1)
Если Вы посмотрите точное определение, то есть еще один компонент: преобразование состояний в выходные символы. Аналогом этого компонента в программировании может служить массив процедур, вызовы которых сопоставлены состояниям, но для принципиальных рассмотрений у нас он не важен.
2)
Конечно же, в каждом конкретном модуле нужно использовать лишь одну из структур, концептуально несовместимых, хотя формально эквивалентных.
3)
Интересно, что необходимость развитых средств поддержки модуляризации программ первоначально провозглашалась для структурного программирования, но оказалась прекрасно приспособлена совсем к другому стилю. Впрочем, в современных программах самый верхний (часто полуавтоматически генерируемый системами визуального программирования и поэтому обычно мало интересный для программистов) этаж структуры программ, как правило, записан именно в стиле автоматного программирования.
4)
Данный абзац добавлен после обсуждения с проф. А.А. Шалыто.
5)
Сделаем общее замечание насчет доказательной силы аргумента: "Это исследовано в теории". При применении теории необходимо всегда помнить, что вовсю исследуются не только разумные понятия, но и извращения.
