УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

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

(c) А.А.Шалыто

3. Графы переходов как язык спецификаций.

3.1. Стратегии синтеза алгоритмов логического управления.

Возможны две стратегии построения алгоритмов этого класса. При применении первой из них считается, что известен алгоритм функционирования объекта управления и требуется по нему синтезировать алгоритм логического управления, обеспечивающий заданное поведение объекта. Приведем в качестве примера фрагмент алгоритма управления клапаном, синтезированный указанным способом: "Для того, чтобы клапан открылся, вычислитель должен на вход открытия исполнительного механизма клапана подавать единичный сигнал".

При второй стратегии, учитывая информацию о состоянии (положении) объекта управления, строится алгоритм, который обеспечивает требуемое функционирование объекта. Например, "если вычислитель выдает на вход открытия исполнительного механизма клапана единичный сигнал, то клапан открывается".

Первая стратегия "направлена" от объекта управления к вычислителю, а вторая - в обратную сторону - от вычислителя к объекту.

Первая стратегия базируется на понятии "состояние", а вторая - на понятии "событие" ("входное воздействие").

Несмотря на то, что в настоящее время при создании алгоритмов управления, например, в форме схем алгоритмов или в виде продукций (секвенций) вида "если...то", обычно используется вторая стратегия, по мнению автора, более естественной для рассматриваемого класса задач является первая из них, так как "состояние" по своей природе статично, а "событие" динамично, и поэтому "управление по состояниям" является более целесообразным, чем "управление по событиям" [33].

Однако ни та, ни другая разновидность управления в общем случае не является исчерпывающей. Только "управление по состояниям и событиям" при этом является корректным. Так как оба понятия "состояние" и "событие" входят в понятие "автомат", то такой вид управления может быть назван "автоматным управлением", а его программная реализация "автоматным программированием".

В предлагаемой в настоящей работе технологии понятие "состояние" является первичным, а понятие "событие" - вторичным, особенно учитывая тот факт, что события, формируемые объектом управления, определяются соответствующими состояниями последнего.

Несмотря на то, что вторая стратегия приводит обычно к построению более компактных и быстродействующих программ, при отсутствии жестких ограничений на объем памяти и быстродействие применение первой из них более естественно, так как соответствует основному принципу управления, применяемому в автоматизированных системах, состоящему в том, что при управлении Оператор сначала определяет состояние объекта, а затем выполняет то или иное действие, порождающее возникновение события.

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

В рамках предлагаемой технологии управление и программирование должны быть автоматными, а построение алгоритмов и программ должно начинаться с формирования дешифратора состояний, а не событий [29], так как при "управлении по событиям" возникают существенные проблемы с введением и корректным использованием внутренних переменных.

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

Если каждому состоянию объекта сопоставить состояние управляющего автомата, которому, в свою очередь, сопоставить вершину графа переходов, а программу, реализующую граф переходов автомата, построить формально и изоморфно, то такая программа будет "понятной" не только Разработчику и Программисту, но и Заказчику, Технологу, Оператору и Контролеру.

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

3.2. Факторы, ограничивающие широкое использование графов переходов в качестве языка алгоритмизации.

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

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

Другая проблема, ограничивающая применение графов переходов, была связана с тем, что при асинхронной схемной реализации систем логического управления из-за состязаний элементов памяти и произвольной дисциплины смены наборов входных переменных реальное поведение схемы может значительно отличаться от поведения модели (графа переходов), по которой схема строилась, что требует в общем случае применения весьма трудоемкого противогоночного кодирования, связанного с избыточностью, часто неприемлемой при аппаратной и в особенности релейно-контактной реализации.

Еще одна из существующих причин состоит в том, что традиционно считалось, что графы переходов описывают только последовательные алгоритмы, которые имеют весьма ограниченное использование в системах управления, для которых характерен параллелизм.

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

3.3. Графы переходов.

Основным понятием, используемым в теории автоматов, является "внутреннее состояние" автомата, которое в дальнейшем будем называть "состоянием".

Это понятие, являющееся одним из основных в поведении человека (здоров - болен, сыт - голоден и т.д.), почему-то обычно не применяется в явном виде при алгоритмизации и программирования процессов управления (за исключением подхода, использованного в объектно-ориентированном анализе [34] и в программных продуктах "S7-HiGraph technology software" [21] и "Modicon State Language" [22]).

При применении других подходов внутреннее состояние Вычислителя обычно либо не учитывается, либо не рассматривается как единое целое. При этом, как в событийно-управляемом программировании, проверяются лишь внешние события и выполняются действия, инициируемые этими событиями, как, например, это имеет место в следующем описании алгоритма: "Если стол накрыт, то Вычислитель должен идти обедать". Такое описание реализуется автоматом без памяти, так как в этом случае и событие и действие являются наблюдаемыми только извне.

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

Применение графов переходов позволяет в явной (графической) форме ввести понятие "состояние" в практику алгоритмизации и программирования по крайней мере для задач логического управления наряду с его применением в теории конечных автоматов, теории линейных систем [35], марковских процессах [36] и в отдельных задачах практического [37] и теоретического [38] программирования. Графы переходов также позволяют в наглядной форме отразить динамику переходов автомата из одного состояния в другое при изменении входных воздействий с указанием значений всех выходных переменных, формируемых в каждом состоянии (для автоматов без выходного преобразователя или автоматов Мура) или во время каждого перехода (для автоматов Мили).

Если в одном автомате используются оба способа формирования значений выходных переменных, то он называется "смешанным" (С-автомат). Если в нем одни и те же переменные применяются как в качестве входных, так и выходных переменных, то такой автомат называется "автоматом с флагами" [29].

Необходимо отметить, что одни и те же наборы значений выходных переменных могут формироваться в разных состояниях, что требует введения дополнительных (промежуточных) переменных для различения этих состояний.

Состояния автомата классифицируют (декомпозируют) все входные переменные на группы, выделяя в каждом из состояний только то подмножество таких переменных, которое определяет требуемые переходы из рассматриваемого состояния в соседние (смежные) состояния, в том числе и в самого себя. При этом входные переменные, не входящие в группу, определенную некоторым состоянием, не влияют на переходы из него в другие состояния, т.е. переходы из рассматриваемого состояния несущественно зависят (не зависят) от всех остальных переменных, не входящих в группу. Это обеспечивает возможность реализации с помощью графов переходов задач большой размерности.

Находясь в некотором состоянии, автомат с памятью превращается в соответствующий автомат без памяти (комбинационный автомат), который по значениям входных переменных, "выбранных" этим состоянием, осуществляет выбор одного из смежных состояний, в состав которых входит и рассматриваемое. Новое состояние "настраивает" автомат на реализацию в общем случае другого комбинационного автомата. Таким образом, автомат с памятью можно рассматривать в качестве многофункционального модуля, настраиваемого состояниями на реализацию в определенной последовательности различных ортогональных систем булевых формул, описывающих комбинационные схемы и зависящих от различных групп входных переменных.

С другой стороны, автомат с памятью можно рассматривать как многофункциональный модуль, настраиваемый на реализацию с помощью входных переменных (значения которых в течение программного цикла обычно не изменяются) автономных (без входных переменных) автоматов.

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

Состояниям автомата в графе переходов соответствуют вершины, а дугам между вершинами - переходы между состояниями (номенклатура составляющих графов переходов минимальна). При этом дуга, представляющая собой петлю, отражает сохранение состояния, в котором автомат находится до тех пор, пока выполняется условие, помечающее петлю. Отсутствие петли свидетельствует о неустойчивости вершины. Автомат может находиться в неустойчивой вершине только один программный цикл. Обычно дуги помечаются булевыми формулами от входных и временных (X и T) переменных. Единичные значения этих формул определяют возможность выполнения переходов. Обратим внимание на тот факт, что даже при наличии петли вершина может быть неустойчивой, если значения формул, помечающие одну из ее входных и одну из ее выходных дуг, не являющуюся петлей, одновременно равны единице.

Значения выходных и временных (Z и t) переменных указываются в явном (битовом) виде в вершинах (для автоматов без выходного преобразователя и автоматов Мура), на дугах (для автоматов Мили) и в вершинах и дугах одновременно (для смешанных автоматов).

Двоичные переменные t управляют функциональными элементами задержки, а двоичные переменные T сигнализируют о срабатывании или несрабатывании этих элементов. При этом будем полагать, что функциональные элементы задержки в состав автоматов не входят и являются для них одним из объектов управления. Комплекс "Автомат - функциональные элементы задержки" образует единую компоненту, называемую "управляющим автоматом".

При чтении графов переходов считается, что в каждый момент времени (за один программный цикл) выполняется не более одного перехода: ни одного, если состояние сохраняется, и один - если оно не сохраняется, что поддерживается соответствующей программной реализацией.

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

3.4. Построение графов переходов.

Пусть требуется построить граф переходов, описывающий поведение автомата с n двоичными входами и m двоичными выходами. Для задач большой размерности построение графа переходов обычно выполняется по словесному описанию условий работы объекта управления, в котором понятие "состояние", являющееся математической абстракцией, естественно, не используется.

Однако если формализацию проводить с помощью графов переходов автоматов Мили, наиболее часто применяемых в литературе для описания примеров автоматов небольшой размерности, то это понятие (абстракция) приходится вводить сразу для различения ситуаций, связанных с изменениями значений выходных переменных при одних и тех же значениях входных переменных. Построение графов переходов в "изменениях" порождает последующие трудности по их чтению (пониманию) и корректировке, так как при этом значения выходных переменных зависят не только от состояния, но и от значений входных переменных, существенных для рассматриваемого состояния.

Если же "состояние" определять как комбинацию значений всех m выходных переменных, причем одинаковые комбинации этих переменных рассматривать как различные состояния, то такое определение существенно менее абстрактно и более естественно. При этом появляется возможность в каждом состоянии иметь информацию о значении каждой выходной переменной, что, по мнению автора, является определяющим для обеспечения в дальнейшем простоты чтения и понимания, а также корректировки графов переходов.

На начальном этапе построения графа переходов число вершин в нем должно быть выбрано так, чтобы каждая из них поддерживала одно из состояний объекта управления (включая состояния, соответствующие его неисправностям) или системы управления (например, состояния, соответствующие неправильным действиям Оператора). В дальнейшем при необходимости может быть сделана попытка минимизации числа вершин. При этом отметим, что в общем случае число состояний в автомате может быть меньше числа состояний объекта, так как одно и тоже состояние автомата может поддерживать с помощью одинаковых значений выходных переменных разные состояния объекта (например, закрытое и открытое состояния клапана "с памятью" (его устойчивые состояния) могут поддерживаться как двумя, так и одним состоянием автомата с нулевыми значениями выходных переменных).

Каждая комбинация значений всех выходных переменных соответствует одной вершине графа переходов и помечает ее. Каждая вершина графа переходов соединяется дугами непосредственно с теми его вершинами, в которые должен "перейти" автомат при выполнении условий, помечающих дуги, причем даже соседние вершины могут быть помечены одинаково. При этом условию соответствует булева формула, а выполнению условия - равенство этой формулы единице на определенных входных наборах, причем каждой дуге соответствует только одна булева формула, зависящая не от всех n входных переменных, а только от того их подмножества, которое семантически определяет переходы из рассматриваемой вершины в соседние, что позволяет строить графы переходов для задач весьма большой размерности.

При такой методике построения заданные условия работы реализуются графом переходов автомата без выходного преобразователя с принудительным [29] кодированием состояний, который в дальнейшем в случае необходимости, например при наличии вершин, помеченных одинаково, и отсутствии различающих входных наборов, преобразуется в граф переходов автомата другого типа с явным введением понятия "состояние" (граф переходов автомата Мура) или другого типа кодирования (граф переходов автомата без выходного преобразователя с принудительно-свободным [29] кодированием состояний), не изменяя структуру первоначально построенного графа переходов. В отдельных случаях учет ограничений требует использования графа переходов смешанного автомата, что приводит к необходимости введения в граф переходов автомата без выходного преобразователя или в построенный по нему граф переходов автомата Мура значений выходных переменных (через дробь с булевой формулой, помечающей соответствующую дугу), формируемых на переходе. При этом необходимо отметить, что граф переходов всегда может быть представлен в виде композиции, состоящей из системы булевых формул автомата без памяти (образованной формулами, помечающими дуги графа переходов) и графа переходов, дуги которого помечены одиночными буквами, каждая из которых заменяет соответствующую формулу.

3.5. Описание функционирования автоматов без памяти.

Применение изложенной методики позволяет реализовать условия функционирования, не различая соответствует ли им автомат с памятью или без памяти. Если для автоматов с памятью построение графа переходов при алгоритмизации является целесообразным, так как в явном виде отражает присущую автоматам этого класса зависимость набора значений выходных переменных по крайней мере от состояния, то для автоматов без памяти, для которых такая зависимость отсутствует, а значения набора выходных переменных в рассматриваемый момент времени зависят только от набора входных переменных в тот же момент времени, в применении графов переходов нет необходимости. Поэтому если удается определить, что граф переходов описывает автомат без памяти или может быть сведен к нему, то граф переходов целесообразно заменить, например, системой булевых формул.

3.6. Свойства графов переходов.

Одно из достоинств графов переходов состоит в том, что они могут быть формально проверены на синтаксическую корректность (смысловая корректность, естественно, формально проверена быть не может). При этом граф переходов считается корректным, если он непротиворечив, полон, не содержит генерирующих контуров, отличных от петель.

При этом считается, что непротиворечивость в графе переходов обеспечивается в том случае, если в нем запрещены одновременные переходы по любым двум или более дугам, исходящим из одной вершины. Если одновременные переходы из одной вершины допустимы, то такие графы переходов, в каждом из которых допустимо одновременное существование нескольких "активных" вершин, называются графами переходов с параллелизмом. Графы переходов с параллелизмом отличаются от диаграмм "Графсет" только отсутствием возможности осуществления внутри одной компоненты синхронизации завершения параллельных процессов. При использовании системы взаимосвязанных графов переходов с параллелизмом и описании каждого алгоритма отдельным графом переходов (компонентой) синхронизация процессов при необходимости осуществляется в головном графе переходов. Поведение графов переходов с параллелизмом (определяемое графом достижимых маркировок, являющимся графом переходов между всеми возможными состояниями компоненты или системы компонент) отличается от его описания: граф переходов с параллелизмом делает "больше", чем описывает его структура.

В этом смысле графы переходов (без флагов и умолчаний зависящих от предыстории значений выходных переменных) аналогичны параллельно-последовательным контактным схемам, для каждой из которых булева формула, описывающая ее структуру, одновременно задает и ее функционирование (поведение), а графы переходов с параллелизмом аналогичны мостиковым контактным схемам, для которых булева формула, описывающая поведение каждой из них, не задает ее структуру.

При этом, если в графе переходов этого типа понятия "вершина" и "состояние" являются синонимами, то для графов переходов с параллелизмом эти понятия не эквивалентны.

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

При формальном (и правильном) переходе от графа переходов к тексту программы это свойство при одних методах реализации может быть сохранено полностью, а при других - частично. Частичность сохранения этого свойства следует понимать в том смысле, что, например, при описании заданного графа переходов (в случае, когда число вершин в нем не равно величине "два в степени") с помощью системы булевых формул и обратном построении графа переходов по этой системе, в новом графе появляются вершины, отсутствующие в исходном задании [39]. Однако так как переходы из вершин заданного графа переходов в новые вершины отсутствуют, то, несмотря на наличие переходов из новых вершин в заданные, такая реализация является корректной.

При реализации графов переходов, с помощью конструкции switch языка Си, указанное свойство ввиду их изоморфизма может быть сохранено полностью [29].

При неформальном переходе от графа переходов к программе поведение последней может отличаться от графа переходов, в том числе и таким образом, что используя его в качестве теста для проверки программы, их несоответствие обнаружить не удается. Это объясняется тем, что в графе переходов пометка практически каждого перехода не зависит от каких-либо переменных из всего множества входных переменных, которые в программе с ошибками могут стать существенными для рассматриваемого перехода. Например, если некоторый переход в графе происходит при пометке x4, а в программе этому переходу соответствует пометка x4&!x5, то такую ошибку без полного перебора или построения графа переходов по программе обнаружить можно только случайно. Это еще раз подтверждает высказывание Э. Дейкстры о том, что с помощью тестов можно обнаруживать все новые и новые ошибки в программе, но нельзя доказать, что их в ней после тестирования не осталось. Именно по этой причине в настоящей работе большое внимание уделяется построению "понятных" Специалистам разного профиля алгоритмов и программ, что должно позволить устранить многие ошибки в них в результате согласования на разных стадиях проектирования, включая и начальные. Формальность и изоморфность построения программы по "понятной" спецификации, для которой также построен (и откорректирован в случае необходимости) граф достижимых маркировок, приводит к тому, что граф переходов может служить не средством отладки, а средством сертификации программ.

Непротиворечивость графов переходов (конъюнкция пометок любых двух дуг, исходящих из одной вершины, равна нулю) обеспечивается:

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

Полнота графа переходов (дизъюнкция пометок всех дуг, исходящих из вершины, равна единице) проверяется после обеспечения непротиворечивости. При реализации графа переходов с помощью системы булевых формул должны быть помечены все дуги, исходящие из каждой вершины, а при других вариантах реализации пометки петель для автоматов без выходного преобразователя или автоматов Мура могут умалчиваться. При этом предполагается, что пометка петли в вершине обеспечивает "полноту" последней.

В графах переходов существуют генерирующие контуры, если по крайней мере в одном из них конъюнкция пометок всех дуг, которые его образуют, не равна нулю. Устранение генерирующих контуров осуществляется теми же методами, что и устранение противоречивости (за исключением расстановки приоритетов).

3.7. Кодирование состояний автоматов.

Для реализации графа переходов его вершины (состояния) должны иметь различные пометки (коды).

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

Если в графе переходов автомата без выходного преобразователя пометки некоторых вершин совпадают, то для их различения вводится минимально необходимое число дополнительных (промежуточных, внутренних) переменных y_i, значения которых различают одинаковые вершины. Этот вид кодирования будем называть принудительно-свободным.

В автоматах Мура, Мили и смешанных автоматах применяется свободное кодирование, при котором коды вершин графов переходов выбираются независимо от значений выходных переменных, связанных с этими вершинами.

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

Из всех видов свободного кодирования при программной реализации автоматов наиболее целесообразно использовать два вида кодирования: двоичное и многозначное (целочисленное).

В первом случае i-й вершине графа переходов присваивается одна двоичная переменная Y_i, принимающая единичное значение только в i-й вершине и нулевое во всех остальных вершинах.

Во втором случае I-му графу переходов в целом присваивается одна многозначная переменная YI, j-е значение которой, в свою очередь, присваивается j-й вершине графа переходов, что обеспечивает реализацию алгоритмов с минимально возможным числом дополнительных переменных. Именно этот вид кодирования и обеспечивает наилучшее чтение программ. Другое достоинство этого вида кодирования состоит в том, что предыдущее значение многозначной переменной нет необходимости сбрасывать принудительно, так как происходит ее автоматический сброс при переходе к другому значению этой переменной. При этом необходимо отметить, что при наличии одной внутренней переменной в одном графе переходов состязания "элементов" памяти отсутствуют, так как этой переменной не с чем "состязаться".

Более того, при корректной организации вычислительного процесса состязания "элементов" памяти отсутствуют при любом виде кодирования: программа может либо правильно, либо неправильно реализовывать заданный алгоритм, так как в отличие от одной асинхронной схемы она не может вести себя по-разному в зависимости от реальных "задержек элементов". Назначение порядка выполнения команд в программе является своего рода синхронизацией. Например, если в качестве языка программирования применяется язык функциональных схем и в базисе этого языка построена некоторая схема, то при допустимости изменений значений входных переменных только в начале программного цикла при одном порядке срабатывания (нумерации) элементов она будет иметь одно полностью детерминированное поведение, а при другой нумерации - другое также полностью детерминированное поведение, причем ни то ни другое поведение может не соответствовать желаемому.

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

Пусть, например, при непосредственном переходе из состояния графа переходов с кодом "00" в состояние с кодом "11" имеет место переключательный процесс "00-10-11", в котором значение "10" является промежуточным и "фильтруется". Переход "00-01-11" при программной реализации с помощью системы булевых формул в отличие от асинхронных схем невозможен, так как порядок изменения значений переменных однозначно определяется порядком расположения формул в системе.

3.8. Особенности использования графов переходов.

При реализации алгоритма одним графом переходов автомата Мура или автомата без выходного преобразователя и формальном переходе к тексту программы по графу переходов без флагов и умолчаний, являющемуся одновременно и графом достижимых маркировок, полностью описывающим поведение автомата, этот граф может служить также и тестом для проверки правильности программы. Если программа в этом случае построена по графу переходов не только формально, но и изоморфно (обеспечена изобразительная эквивалентность между графом переходов и текстом программы), то тестирование может быть заменено сверкой ее текста с графом переходов.

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

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

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

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

3.9. Основные этапы алгоритмизации при использовании графов переходов.

Разрабатывается схема связей "источники информации - управляющий автомат - средства представления информации - исполнительные механизмы".

Управляющий автомат декомпозируется на автомат и функциональные элементы задержки, что позволяет исключить время из модели, оставив только битовые переменные t, предназначенные для запуска функциональных элементов задержки (выходы автомата) и битовые переменные T, сигнализирующие о срабатывании этих элементов (входы автомата). При этом предыдущая схема преобразуется в схему связей "источники информации - автомат - функциональные элементы задержки - средства представления информации - исполнительные механизмы".

При необходимости автомат эвристически декомпозируется на систему взаимосвязанных автоматов меньшей размерности. Декомпозиция может производиться по режимам, объектам или смешанным образом.

Построение схемы связей "источники информации - система взаимосвязанных автоматов - функциональные элементы задержки - средства представления информации - исполнительные механизмы" завершает стадию архитектурного (системного) проектирования.

Рассматривая i-й автомат вместе с управляемыми им функциональными элементами задержки в качестве i-го управляющего автомата, можно считать, что последняя схема содержит систему взаимосвязанных управляющих автоматов.

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

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

На третьей стадии проектирования при необходимости осуществляется выбор, построение и оптимизация алгоритмических моделей, реализующих формальные спецификации, с учетом рода (первого или второго) принятой структурной модели каждого автомата с памятью, например автомата Мура второго рода [39].

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

При этом, естественно, что и графы переходов также являются алгоритмической моделью, перед программированием которой необходимо знать род выбранной структурной модели.

Выбор той или иной алгоритмической модели зависит от используемого языка программирования. При этом для некоторых языков, например Си, может применяться любая из перечисленных моделей, а для других, например функциональных схем, число таких моделей ограничивается одной.

После выбора алгоритмических моделей для реализации формальных спецификаций осуществляется переход к последней (четвертой) стадии предлагаемой технологии - программированию. На этой стадии после выбора языка программирования для каждой алгоритмической модели должен осуществляться выбор программной модели, содержащей в частности перечень используемых операторов.

Развернутый пример, иллюстрирующий использование предлагаемого подхода, приведен в [40].

3.10. Программирование.

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

В первом случае доказательство эквивалентности программы с графом переходов, по которому она строилась, может производиться их сопоставлением. При этом граф переходов всегда может быть восстановлен непосредственно по тексту программы без дополнительных вычислений.

Во втором случае читать программу трудно, но в этом и нет необходимости, так как она формально строится по графу переходов, который и следует читать. Проверка программы в этом случае может производиться, используя граф переходов в качестве теста, по "схеме": настоящее состояние, вход - следующее состояние, выход. Верификация, состоящая в построении графа переходов, в этом случае существенно более трудоемка и связана с вычислениями. Изоморфизм между текстом программы и графом переходов, естественно, обеспечивается за счет избыточности, использование которой невозможно при жестких ограничениях на объем памяти.

Главная особенность предлагаемых программных реализаций состоит в том, что за один программный цикл в программе выполняется не более одного перехода в графе переходов. В противном случае, если для некоторой вершины графа переходов автомата Мура условия, помечающие одну из входящих и одну из исходящих (кроме петли) дуг, выполняются, то значения выходных и внутренних переменных, которые должны быть сформированы в этой вершине, будут отфильтрованы (пропущены).

Название предлагаемой технологии порождено конструкцией switch языка Си, так как ее использование позволяет наиболее просто переходить от построенного графа переходов к изоморфному по структуре тексту программы. Оператор switch, осуществляющий многовариантный (многозначный) выбор, обеспечивает в данном случае декомпозицию автомата по его внутренним состояниям.

3.11. Программная и методическая поддержка технологии.

Возможность быстрого, безошибочного и изоморфного перехода от графа переходов к тексту программы на языке высокого уровня, например Си, позволяет резко упростить отладку и моделирование управляющего автомата, а при необходимости и комплекса "управляющий автомат - объект управления", описав не только автомат, но и модель объекта управления (по компонентам и/или режимам) с помощью графов переходов.

Под руководством автора разработана программная оболочка, позволяющая на персональном компьютере для системы взаимосвязанных графов переходов, состоящей из N графов переходов, реализованных на языке Си, изменять с помощью клавиатуры значения входных переменных и наблюдать на дисплее значения выходных, временных, а самое главное, N внутренних переменных (всего по одной внутренней переменной для каждого графа переходов) в пошаговом и автоматическом режимах.

Возможность постоянного чтения на дисплее десятичного номера состояния каждого графа переходов в каждом программном цикле с помощью всего лишь одной многозначной переменной делает программу полностью наблюдаемой и управляемой, что принципиально отличает предлагаемую технологию от традиционных технологий программирования, при использовании которых всегда имеются возможности вызова с помощью отладчика на дисплей любой переменной и слежения за изменениями ее значений. Однако при этом практически всегда остаются не ясными ответы на следующие вопросы:

• какие переменные следует применять в программе для обеспечения ее работоспособности и управляемости;
• сколько таких переменных (особенно внутренних) следует применять;
• что характеризует каждая переменная;
• какой набор переменных следует выводить на дисплей на каждом этапе отладки;
• какие переменные следует дополнительно ввести в программу и представить на дисплее, если на некотором этапе отладки её работоспособность еще не обеспечена.

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

Если в качестве языка программирования применяется алгоритмический язык высокого уровня, например Си, то после построения алгоритма по предлагаемой технологии, включая его сертификацию и моделирование с помощью указанной оболочки, разработка программы завершается. При использовании других типов языков программирования после этого осуществляется формализованный (ручной или автоматический) переход (синтез) от построенной программы к тексту программы на применяемом языке.

Например, для программируемых логических контроллеров "Autolog" фирмы "FF-Automation" Б.П. Кузнецовым (НПО "Аврора") совместно с автором разработан транслятор "язык Си - язык ALPro", позволяющий по тексту структурированной программы, написанной по графу переходов на некотором подмножестве языка Си, автоматически получать программу на языке инструкций ALPro с выбранными до трансляции управляющими конструкциями условным переходом или шаговым регистром [3].

При ограничениях на внутренние ресурсы программируемых логических контроллеров автором разработана методика "ручной" формальной реализации графов переходов в базисе языка ALPro. Разработаны также методики реализации графов переходов в базисе таких языков программирования, как лестничные и функциональные схемы [39]. Одна из этих методик позволяет, в частности, строить функциональные схемы, изоморфные графы переходов, в базисе библиотечных элементов для системы "Selma-2" [41].