[ <<< | Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]
Граф переходов ПСА может содержать дуги, помеченные одинаковыми парами “событие / действие” и направленные в одну и ту же вершину. Такой автомат не является БПСА, но при определенных условиях может быть преобразован в последний.
Рассмотрим такой ПСА, граф переходов которого изображен на рис. 8а (для упрощения рисунка петли у вершин не показаны). Дуги ab, cb, db направлены в вершину b и имеют одинаковые пометки “T1 / Y1”. Налицо явный повтор переходов. При выполнении указанных позже условий можно преобразовать данный повторный автомат в бесповторный. Для реализации такого преобразования введем в граф переходов дополнительную вершину, так называемого обобщенного состояния. Последнее обозначается списком идентификаторов вершин, из которых исходят упомянутые, одинаково помеченные и направленные, дуги. В нашем примере на рис. 8б представлена (штриховым контуром) вершина обобщенного состояния, помеченная списком “a, c, d”. Из этой вершины исходит дуга, направленная в вершину b и помеченная парой “T1 / Y1”. Дуги, помеченные аналогично на рис. 8а, исключены в новом графе переходов. Полученный таким образом автомат является бесповторным, так как не содержит одинаково помеченных дуг на графе переходов.
Такой БПСА реализуется следующим образом. После исполнения пролога проверяется текущее состояние БПСА, и, если оно входит в список, отмечающий обобщенное состояние, то реализуется попытка получения события T1. При наличии T1 выполняется подпрограмма Y1 и осуществляется переход в состояние b, после чего реализуется эпилог и выход из подпрограммы БПСА до следующего глобального цикла. При отсутствии события T1 реализуется соответствующий переход из штатных вершин.
Таблица – список событий БПСА с обобщенным состоянием в качестве первой строки после строки пролога содержит в графе “текущее состояние” список идентификаторов, отмечающих обобщенное состояние и соответствующую информацию по формированию события T1 в остальных графах. Список событий и блок-схемы реализации БПСА с обобщенным состоянием не приводятся в целях экономии объема статьи.
Перейдем к рассмотрению условий получения обобщенного состояния. Помимо описанного (первого) условия наличия одинаково помеченных и направленных переходов существует еще два условия.
Второе условие состоит в том, что прологи тел состояний, из которых осуществляется указанный переход, должны быть одинаковыми, в том числе пустыми (отсутствующими), или трехполюсник, реализующее повторяющееся событие, не зависит от прологов указанных состояний.
Третье условие предполагает, что трехполюсники, реализующие одинаковые повторяющиеся события, должны быть первыми в соответствующих состояниям (с указанным событием) многополюсниках, или могут быть переставлены на первое место. Рассмотрим последнее утверждение.
В [5] дано понятие о независимых и зависимых фрагментах – двухполюсниках. Аналогичное понятие введем и для трехполюсников, входящих в подпрограммы-многополюсники Zi.
Допустим в многополюснике Zi имеются два трехполюсника, описываемых выражениями
“T1 = [A1 -> X1]” и “T2 = ~T1 & [ A2 -> X2]”.
Если допустимо их преобразование к виду
“T2 = [A2 -> X2]” и “T1 = ~T2 & [A1 -> X1]”,
то есть выполняется перестановка трехполюсников без потери сущности событий T1 и T2, то такие трехполюсники будем называть независимыми. Если перестановка трехполюсников в указанном смысле недопустима, то такие трехполюсники будем называть зависимыми.
Следовательно, конкретный трехполюсник может быть переставлен на первое в многополюснике место, если он и выше расположенные трехполюсники независимы.
В общем случае, число обобщенных состояний может быть два и более, но в данной статье этот вопрос обсуждаться не будет.
Представленные графы переходов БПСА воспринимаются сложнее, чем традиционные АНС, хотя список событий читается сравнительно легко. С целью приведения БПСА к виду, напоминающему традиционный самодостаточный граф переходов АНС, выполняется декомпозиция состояний на основе вычленения отдельных трехполюсников из многополюсников. Покажем на примере как это делается.
Возьмем граф переходов БПСА, изображенный на рис. 4, и дополняющую его табл. 1. Составим на их базе новый граф переходов с числом вершин, равным числу вершин исходного графа плюс число событий. Вершины расположим в 4 горизонтальных ряда, соответствующих состояниям рассматриваемого БПСА.
Каждый ряд включает начальную вершину, реализующую пролог состояния, и вершины, реализующие события, инициируемые в указанном состоянии. В частности первый ряд (рис. 9) соответствует состоянию “a” исходного графа переходов и включает вершины: “a0” – вершина, реализующая пролог P1, “a1” – вершина, реализующая действие А1 и инициирующая событие T1, “a2” – вершина, реализующая действие А2 и инициирующая событие T2. Из вершины “a0” в вершину “a1” направлена непомеченная условием и действием дуга скрытого перехода. Из вершины “a1” в вершину “b0” (состояние “b” исходного БПСА) направлена дуга , помеченная условием X1 и действием Y1 (реализация события T1). Из той же вершины “a1” в вершину “a2” направлена дуга скрытого перехода, помеченная условием ~X1 (не состоявшееся событие T1). Из вершины “a2” в вершину “b0” направлена дуга, соответствующая реализации события T2, а в вершину “a0” направлена дуга, реализующая петлю “~T2 / W1” исходного графа переходов. Аналогично строятся остальные вершины и дуги нового графа переходов БПСА.
От графа переходов АНС полученный на рис. 9 граф отличается отсутствием петель и наличием скрытых переходов. Этот граф напоминает Р-схему [10], но отличается от последней наличием скрытых переходов.
Состояния полученного графа будем называть “субсостояниями” БПСА. Субсостояния, связанные скрытыми переходами, вкупе соответствуют состоянию исходного графа переходов.
Отметим так же, что на рис. 9 не указаны пролог P0 и эпилоги из-за ограниченности места. На самом деле в состояниях “a0”, “b0”, “c0”, “d0” перед обозначением пролога состояния должно присутствовать обозначение пролога БПСА P0. Каждая дуга, не являющаяся скрытым переходом, должна быть помечена дополнительно действиями – эпилогами состояния и БПСА. Например, вместо указанной на рис. 9 пометки “X1 / Y1” следует написать пометку “X1 / Y1, E1, E0”.
Таким образом исходный БПСА декомпозируется в граф переходов с субсостояниями и скрытыми переходами, не требующий дополнения в виде списка событий.
Имеет место обратная задача – получить по такому графу список событий, которую здесь не рассматриваем.
[ <<< | Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]