учебники, программирование, основы, введение в,

 

Автоматное программирование: анализ задачи

Автоматные задачи
Многие программистские задачи удобно решать с помощью методов, формализацией которых могут служить таблицы состояний и переходов.
Пример 9.1.1. Модель изменяющейся системы.
Пусть мы моделируем динамическуюлибо экологическую систему, у которой в различных областях принципиально разное поведение. Вместо того, чтобы совмещать внутри одного и того же программного модуля анализ, какой области принадлежит точка, и вычисление следующего состояния системы, мы можем написать несколько простых модулей моделирования поведения системы в каждой из областей (единственная проверка, которая при этом может понадобиться, вышли мы при очередном шаге моделирования за границы области или нет). Как отдельный модуль строится глобальная управляющая программа, которая проверяет, в каком состоянии находится система, и вызывает соответствующий вычислительный модуль.
В данном случае выигрыш не столько в длине программы, сколько в ее обозримости и модифицируемости (хотя именно эти важнейшие качества программы начинающие программисты чаще всего недооценивают). Но если при входе в новую область нужно проделать ряд организационных действий (в каждой области различных), а уже в зависимости от их результата выбрать дальнейшую траекторию системы, то описание в виде автомата становится все более выигрышным.
Если при анализе задачи удается выявить набор состояний описываемого процесса, условия перехода между состояниями и действия, ассоциированные с состояниями, то задачу уместно решать методами таблиц состояний. При анализе таких методов можно применять конечные автоматы Мура.
Теоретически автомат Мура представляется как матрица переходов, строками которой служат состояния автомата, а столбцами - входные символы. В качестве входных символов на практике можно рассматривать результаты проверки некоторых условий. Неявное в теории, но важнейшее на практике содержимое каждого состояния автомата - процедура, приводящая к глобальному изменению состояния вычислительной системы. Такие процедуры назовем действиями.
Таблицы автоматов часто также представляются в виде графов, что особенно удобно, когда не все возможные переходы между состояниями реализуемы.
Здесь состояния идентифицируются порядковыми номерами, а воздействия - буквами.
На таблице состояний или на ее графовом аналоге все действия предполагаются по умолчанию глобальными, и каждое действие соединено с распознаванием, какое из перечисленных на выходящих из него ребрах условий выполнено. В зависимости от того, какое из них выполнено, автомат переходит в соответствующее состояние, которому опять-таки, если оно не заключительное, сопоставлено действие и распознавание.
Имеется вариация понятия автоматов, порождающая другой метод автоматного программирования. В теории автомат Мили отличается тем, что результат, записываемый на выходную ленту автомата, может зависеть от выбранного перехода. На практике действия в таблице состояний и переходов могут ассоциироваться либо с состояниями (с вершинами графа, автомат Мура), либо с переходами (с дугами графа, автомат Мили). Ниже Вы увидите примеры, когда при программировании естественно возникают оба этих варианта. Модель вычислений автомата Мили лучше использовать, если проверки в каждом состоянии по существу различны, а модель автоматов Мура - если проверки по существу однородны, как в примере 9.1.1.Метод программирования, когда действия сопоставляются переходам, назовем преобразованиями на переходах (сокращенно просто "на переходах"), метод, когда действия производятся в состояниях, назовем преобразованиями в состояниях (сокращенно просто "в состояниях").
Заметим, что естественно рассматривать таблицы состояний и переходов как недетерминированные, поскольку после выполнения действия вполне может оказаться истинно сразу несколько условий, соответствующих выходящим ребрам.
Внимание!
В данном случае мы видим один из неистощимых источников ошибок в программах, который впервые заметил Д. Грис. Если по сути задачи нам все равно, какое из действий будет выполнено, а язык (как те стандартные языки, на которых обычно работают) заставляет детерминировать переходы, либо ранжировав их по порядку, либо принудительно сделав их условия логически противоречивыми, то при изменении программы часто возникают трудности. Они связаны с тем, что после изменения детерминировать-то надо было по-другому, но уже нельзя различить, какие из условий существенны, а какие вставлены лишь для детерминации.
Как было показано в нашем примере, таблицы переходов и состояний являются естественным способом программирования для модуля, имеющего дело с глобальными операциями над некоторой средой (эти глобальные операции сами, как правило, программируются в другом стиле). Для автоматного программирования характерно go to, и здесь оно на месте.
Есть много конкретных методик автоматного программирования, укладывающихся в рамки двух главных методов. Автоматное программирование хорошо демонстрирует то, как варьируются практические методы решения логически и математически, вроде бы, однородных задач. Небольшое изменение в ресурсных ограничениях - и, хотя старые методы, как правило, остаются уместными, но лучше перейти к другим.

http://localhost:3232/img/empty.gifОсновные структуры автоматного программирования

Информационное пространство всех блоков и процедур при автоматном программировании в первом приближении одно и то же: состояния системы, моделируемой совокупностью программных действий. Но на самом деле многие блоки либо процедуры работают с подсистемами. Подсистемы, ввиду их автономности, могут иметь характеристики, прямо недоступные для общей системы, и ограниченный доступ к общему системному пространству данных. Более того, подсистемы могут общаться прямо, в обход иерархически вышестоящей системы. Таким образом, структура информационного пространства при автоматном программировании в общих чертах соответствует той, которая навязывается современными системами с развитой модульностью. В системах модульности есть понятия, предоставляемые для пользования другими модулями, есть модули, которые автоматически получают доступ ко всем понятиям дружественного модуля, и есть интерфейсы между модулями.
Светло-серые области - традиционный общий контекст системы и подсистемы. Темно-серые иллюстрируют, что доступность может быть односторонней, и не только по иерархии. Одна из систем может влиять на часть информационного пространства другой, а та может лишь пассивно следить, что натворил коллега. Области, связанные двусторонними стрелками, иллюстрируют прямое общение в обход иерархии.
Исторически первой моделью автоматного программирования, использованной как на практике, так и для теоретических исследований, было представление программы в виде блок-схемы, узлы которой являлись состояниями. Узлы блок-схемы делятся на пять типов:

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

Представление программ в виде блок-схем было целесообразно для многих классов программ, писавшихся в машинных кодах без средств автоматизации программирования. Блок-схемы тогда были основным средством планирования разработки программ и их документирования. Традиционные блок-схемы - предмет изучения, в частности, теоретического программирования.
Таблицы переходов концептуально противоречат такому фундаментальному понятию программирования, как присваивание. В блок-схеме произвольной формы исключительно трудно проследить, как будет изменяться значение переменной, какие существуют зависимости между данными переменными, и т. п.
Действия в автоматном программировании глобальны, а условия локальны. Проверка условия не изменяет состояния всей системы (ни одного из ее параметров или характеристик), она лишь переводит саму программу в то или иное состояние.
Это подтверждает и анализ практических систем, для моделирования которых удобно применять автоматное программирование. Например, открытие или закрытие одного вентиля в трубопроводной системе изменяет все потоки в системе, а проверка - открыт ли вентиль - локальная операция. Изменение температуры рабочего вещества в системе опять-таки влияет на все ее характеристики, а измерить эту температуру можно, сняв показания всего одного датчика.
Здесь мы сталкиваемся с необходимостью четко различать внешние понятия, описывающие систему, которая связана с решаемой программой задачей, и внутренние понятия самой программы. Для системы в целом безразличны состояния автомата, который ее моделирует либо взаимодействует с ней. Для нее важно, какие изменения в ней самой происходят. Таким образом, состояние памяти вычислительной системы вполне может рассматриваться как внешняя характеристика по отношению к программе, которая в ней работает.
Необходимость одновременного и согласованного рассмотрения внешних и внутренних характеристик приводит к тому, что, когда внутренние характеристики раздробляются и детализируются (например, при соединении стиля автоматного программирования с присваиваниями), программист начинает путаться, согласованность понятий исчезает и возникают ошибки.
Внимание!
Если пользоваться произвольными таблицами переходов, то надо позаботиться о том, чтобы присваивания встречались как можно реже, в идеале обойтись без них совсем либо присваивать лишь значения переменным, которые немедленно после этого используются в качестве основания для выбора в операторе типа case.
Граф состояний и переходов, называемый также таблицей переходов — нагруженный ориентированный граф G. Каждой вершине графа G сопоставлено наименование состояния, а каждой дуге — условие.
Условие AB, сопоставленное дуге, ведущей из a в b, содержательно интерпретируется следующим образом. При выполнении AB в состоянии a управление передается состоянию b (или же в другом смысле осуществляется переход по данной дуге).
Когда граф состояний и переходов используется для документирования программы, наименования состояний, как правило, совпадают с именами процедур, выполняющихся в данном состоянии.

http://localhost:3232/img/empty.gifПрограммные представления графа состояний

Отметим, что программные представления графа состояний сильно зависят от динамики данного графа. Стоит выделить четыре подслучая.

  1. Состояния и таблица переходов жестко заданы постановкой задачи (например, такова задача синтаксического анализа). В этом случае лучшее программное представление переходов между состояниями - go to, независимо от размера таблицы.
  2. Состояния и таблица переходов пересматриваются, но фиксированы между двумя модификациями задачи. При небольших размерах таблицы по-прежнему предпочтительней всего реализация через переходы, а при достаточно больших - необходима ее декомпозиция, в связи с чем часто целесообразно представление состояний объектами.
  3. Состояния и таблица переходов динамически порождаются перед выполнением данного модуля и фиксированы в момент его выполнения. Лучший способ реализации - задание таблицы переходов в виде структуры данных и написание интерпретирующей программы для таких таблиц.
  4. "Живая таблица": модифицируется в ходе исполнения. Пока что дать методологические советы для таких таблиц мы не можем, хотя очевидно, что, несмотря на внешнюю рискованность, такой путь чрезвычайно выигрышен для многих систем адаптивного реагирования. Заранее нужно обговорить, что модули, перестраивающие таблицу, и модули, исполняющие ее, должны быть как можно более жестко разделены.

Методы действий в состояниях и на переходах: анализ состояний и построение таблицы
В данном разделе начинается детальный показ двух методов автоматного программирования, основанных на модели Мура и Мили. Методика работы в них почти одна и та же, но, как чаще всего бывает, маленькое и вроде бы техническое различие (чему сопоставляются действия: состояниям или переходам?) порождает два несовместимых метода. Их несовместимость не столь грубая, как во многих других случаях (два таких случая - несовместимость между автоматами и присваиваниями и между циклами и рекурсиями - рассмотрены ниже). Если это и противоречие, то противоречие технологическое. Произвольно перемешивая эти два метода, мы в дальнейшем затрудняем модификацию программы, а в настоящем вынуждены множить число подпорок.
Человек даже грубые противоречия игнорирует или обходит. Для применения правила важно знать не только его, но и когда можно его нарушать. Общеметодологический принцип здесь такой: если уж нарушать, то на полную катушку (проехав перекресток на красный свет, глупо останавливаться сразу за ним)! Второй принцип: если нельзя, но очень нужно, то надо! А. А. Шалыто указал, что в теории есть и такое смешанное понятие, как автоматы Мили-Мура. Одной из моделей таких автоматов является автомат с двумя выходными лентами: на одну пишется результат в состояниях, на другую - на переходах. Программной интерпретацией такой теоретической модели является, например, модуль, который в состояниях ведет диалог с окружающей средой, в результате чего получает данные для определения очередного перехода, а на переходах производит внутренние вычисления.
Для отработки методики используется простая задача, не затемняющая ее суть частными тонкостями и пригодная для реализации любым из двух методов. Полученная методика переносится на широкий класс задач и не отказывает вплоть до тысяч состояний.
Постановка задачи и первичный анализ
Пусть требуется решить следующую задачу. Словом называется любая непустая последовательность букв латинского алфавита (для простоты - только строчных букв). Перепечатать из входной последовательности символов все максимальные входящие в нее слова в следующем виде:
<слово> - <длина слова><конец строки печати>
Ввод заканчивается пустой строкой.
Например, по строкам
попугай бегемот
1мот2крот1мот
нужно выдать что-либо вроде
попугай 7
бегемот 7
мот 3
крот 4
мот 3
Для решения задачи входную последовательность символов естественно считать потоком, читаемым слева направо, пока не будет прочитана пустая строка. При чтении букв, других символов и конца строки действия, которые необходимо выполнять, различны. Кроме того, различаются действия для первой буквы и для последующих букв слова.
Построение графа состояний
Прежде всего, определим набор состояний, исходя из различных реакций на прочитанный символ.
Вот полный перечень вариантов реакций:

  1. Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).
  2. Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).
  3. Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).
  4. Символ не буква: пропустить символ.
  5. Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).
  6. Символ конец строки: пропустить символ.
  7. Символ конец строки: завершить процесс.

Есть еще одно действие, не отраженное в этом списке, но подразумеваемое: стандартное действие, происходящее перед началом отработки нового состояния. В данном случае это чтение очередного символа, которое должно выполняться, когда переход срабатывает. В других случаях автоматных моделей роль чтения очередного символа может играть, скажем, последующий шаг моделирования. Для данного и для большинства других автоматных примеров стандартное действие не нужно указывать явно, поскольку оно автоматически сопоставляется каждому переходу и полностью соответствует математической модели.
Из перечня действий для рассматриваемой задачи следует, что должно быть, как минимум, два класса состояний, имеющие разные действия-реакции.
Следующий методический прием - это определение начального состояния, т. е. того, в котором вычислительный процесс активизируется. Нужно указать, какие действия возможны в данном состоянии и какие условия перехода в нем должны быть.
Для рассматриваемого случая в начальном состоянии (St1), возможны переходы:

  1. с переходом в другое состояние - St2 (поскольку следующая буква требует другой реакции),
  1. с сохранением состояния и
  1. отработка первого перевода строки.

Результат только что проведенного анализа можно представить в виде графа, изображенного на. С каждой дугой графа связано условие перехода. С каждым состоянием может быть связано действие. В состояниях St1 и St3 действием является пропуск очередного символа и чтение следующего, но соединить их сейчас нельзя, поскольку в первом из них переход на завершение работы невозможен, так что перевод строки анализируется по-разному. Это позволяет предположить, что в данной задаче действия стоит ассоциировать с переходами, а не с состояниями. Правильный выбор того, с чем ассоциировать действия, может сильно оптимизировать программу. Для показа двух возможных вариантов, которые в данном случае почти эквивалентны по сложности, мы будем действовать как на переходах, так и в состояниях. В частности, предварительный анализ состояний при методе преобразований на переходах дан на.
Внимание!
Если у Вас есть две близкие, но концептуально противоречивые, модели, в начале развития программы нужно сделать выбор в пользу одной из них. Небольшие эксперименты и отступления в начале оборачиваются большой экономией сил в конце.
На схемах вход и выход обозначаются черными прямоугольными блоками. При желании их можно считать специальными состояниями, с которыми ассоциированы действия инициализации и завершения процесса. Состояние St2 изображено штриховой линией, поскольку анализ его еще не проведен. Для каждого из еще не проанализированных состояний (в данном случае для St2) следует определить условия перехода (и соответствующие им действия, если выбрали работу на переходах).
В рассматриваем случае в состоянии St2 возможны переходы:

  1. с сохранением состояния;
  1. окончание слова и отработка вывода слова, поскольку следующий символ не буква, с переходом в другое состояние, которому дается временное имя St4;
  1. отработка окончания слова и перевода строки, ему можно дать временное имя St5.

После этого построения проверяется, не является ли новое состояние копией уже имеющихся как по действиям, так и по переходам. Если это так, то новое состояние можно отождествить (склеить) с одним из ранее построенных. Вновь появляющиеся состояния анализируются аналогично.
Для решаемой задачи легко выяснить, что состояние St3 требует тех же действий и переходов, что и St5, а St4 изоморфно St1. Следовательно, возможна склейка этих двух состояний со старыми и построение графа завершается, так как новых состояний нет. С тем, чтобы не дублировать действия <Завершить процесс>, можно определить еще одно, заключительное состояние, с выходом из которого будет ассоциировано это действие (один раз!).
Аналогично можно поступить и когда мы работаем в состояниях. Здесь процесс удлиняется на один шаг, поскольку необходимо выделить завершение обработки слова в отдельное действие (причем в двух вариантах: после перевода строки и после других небуквенных символов). Полученный результат показан на.
Табличное представление графа состояний
Графическое или иное представление графа состояний конечного автомата, явно отражающее наименования состояний, условия переходов между состояниями и ассоциированные с ними действия, называют таблицей переходов. Такое представление является одним из центральных компонентов широко используемого в индустриальном программировании языка объектно-ориентированного дизайна UML (в частности, в форме, реализованной в системе Rational Rose) - state transition diagrams (диаграммы состояний и переходов).
Различают визуальные представления таблиц переходов, которые предназначены для человека, и их программные представления. Требования к визуальным представлениям - понятность для человека, статическая проверяемость свойств; требования к программным представлениям - выполнимость при посредстве какой-либо системы программирования; общее требование к представлениям обоих видов - однозначное соответствие между ними, позволяющее обоснованно утверждать вычислительную эквивалентность.
Ответ на вопрос, какое представление графа состояний лучше всего использовать, зависит от сложности графа, статичности либо динамичности его и того, для каких целей требуется спецификация в виде графа состояний. Понятно, что важнейшей для нас промежуточной целью является программа на алгоритмическом языке. Но подходы к построению такой программы могут быть различны. Существует две принципиально различные методики применения спецификаций:

  • трансляционная - генерируется программа, структура управления которой определяется графом состояний;
  • интерпретационная - строится специальная программа, которая воспринимает некое представление графа как задание для интерпретации.

Как при трансляционной, так и интерпретационной позиции возможен целый спектр реализаций. Ближайшая же цель в том, чтобы научиться удобно для человека представлять граф состояний и переходов. Наиболее естественно описывать его в виде таблицы. Для методов на переходах и в состояниях таблицы несколько различаются. На табл. 9.1 представлен случай Мили. Опишем значение колонок таблицы.

  1. Наименование состояния - входы в таблицу.
  2. Условие (срабатывания) перехода - логическое выражение или служебное слово failure, которое указывает на действие, выполняемое, если ни одно из условий не срабатывает.
  3. Действие, ассоциированное с переходом, - последовательность операторов, выполняемая, когда условие перехода истинно.
  4. Адрес перехода - наименование состояния-преемника.

Кроме того, определяется специальная (первая) строка, в которой помещаются операторы, инициирующие процесс, и адрес перехода начального состояния.
В табличном представлении графа переходов в состояниях (таблица 9.2) действия помещаются во втором столбце, сразу после обозначения состояния, а уже затем идут переходы. Анализируя таблицу 9.2, можно заметить ряд повторяющихся действий. Конечно же, если бы эти действия были более сложными, их просто описали бы как процедуры. Но такие повторения заставляют задуматься, а нельзя ли сократить число состояний? Введя дополнительную булевскую переменную, отметившую, что последним символом был перевод строки, мы могли бы избавиться от пары состояний. Но такой переменной нужно присваивать новое значение в процессе проверки условий, и при этом в строго определенный момент: сначала проверить, не является ли символ концом строки, а уже затем переприсваивать данную переменную. Это решение сильно отдает хакерством, и, если Вы хотите писать качественные, легко перестраиваемые программы, то таких решений нужно избегать.
Еще раз показать тонкую грань между хакерством и естественностью можно, рассмотрев один из моментов, возникающих в наших программах. При работе в состояниях нам приходится обнулять счетчик букв слова в тот момент, когда кончается очередное слово, поскольку иначе пришлось бы выделять еще одно состояние, соответствующее середине обработки слова. Но это гораздо менее искусственное решение: неплохо восстанавливать начальные значения и делать другие действия по приведению в порядок информации в тот момент, когда заканчивается очередной этап работы; неплохо делать это всегда в начале нового этапа; плохо лишь произвольно перемешивать эти две дисциплины.


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

char symbol; // Чтение потока символов неявное
// Чтение происходит перед выполнением проверок и действий
int Cnt; . . . // Инициализация

St1

St1

'a'<=symbol && symbol <= 'z'

printf ("%c", symbol); Cnt = 1;

St2

/*(symbol<'a'|| 'z'<symbol) &&*/ symbol!='\n'

/* Действий нет */

St1

symbol='\n'

/* Действий нет */

St3

St2

'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

St3

'a'<=symbol && symbol <= 'z'

printf ("%c", symbol); Cnt = 1;

St2

/*(symbol<'a'|| 'z'<Symbol) &&*/ symbol!='\n'

/* Действий нет */

St1

symbol='\n'

Второй '\n' дальше не нужно читать

exit

exit

/* Нет неявного чтения потока */

return 0; // Считать данную секцию таблицы состоянием или нет - дело вкуса

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

char symbol; // Чтение потока символов неявное
// Чтение происходит после выполнения действия, перед проверками
int Cnt; ...Cnt=0;
// Инициализация

St1

St1

/* Действий нет */

'a'<=symbol && symbol <= 'z'

St2

/*(symbol<'a'|| 'z'<symbol) &&*/ symbol!='\n'

St1

symbol='\n'

St3

St2

printf ("%c", symbol); Cnt++;

'a'<=symbol && symbol <= 'z'

St2

/*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n'

St4

symbol='\n'

St5

St3

/* Действий нет */

'a'<=symbol && symbol <= 'z'

St2

/*(symbol<'a'|| 'z'<Symbol) &&*/ symbol!='\n'

St1

Второй '\n' дальше не нужно читать symbol='\n'

exit

St4

printf ("- %i\n", Cnt); Cnt=0;

'a'<=symbol && symbol <= 'z'

St2

/*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n'

St1

symbol='\n'

St3

St5

printf ("- %i\n", Cnt); Cnt=0;

'a'<=symbol && symbol <= 'z'

St2

/*(symbol<'a'|| 'z'<symbol) &&*/ symbol != '\n'

exit

Второй '\n' дальше не нужно читать symbol='\n'

exit

exit

/* Нет неявного чтения потока */

return 0; // Считать данную секцию таблицы состоянием или нет - дело вкуса

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gif

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика