Необходимые условия для выделения части конечного автомата в метод
Автоматизация проведения преобразований для крупных конечных автоматов является исключительно важной задачей, ибо сложность проводимого анализа способствует возникновению ошибок. Одним из этапов процесса автоматизации является возможность автоматического поиска частей конечного автомата, которые можно поместить в отдельный метод согласно описанным выше подходам. После выделения одного метода могут появляться новые группы состояний, удовлетворяющие условиям выделения метода; поэтому необходимо иметь возможность автоматически выполнять итеративный поиск с возвращением для выявления наиболее оптимальной последовательности трансформаций.
Всё сказанное выше подтверждает актуальность и востребованность следующей задачи: сформулировать достаточно формальные необходимые условия для выделения части конечного автомата в метод, общие для всех предложенных трансформаций. Ниже приводятся такие условия.
Обозначим переход из состояния а в состояние b по событию sig, выполняющий действия act, через t (a?>b; sig; act). Обозначим конечное состояние автомата через stop, ветвление по условию cond через decision (cond), а конечное состояние процедуры (возврат из процедуры) через return. Тогда, например, переход из ветвления по условию cond в конечное состояние автомата будет обозначаться как t ( decision (cond)?> stop; sig; act).
На диаграмме конечного автомата, записанной в нотации UML, кроме стрелок, обозначающих переходы, могут присутствовать следующие элементы: состояния автомата, символы ветвления по условию (decision), начальное состояние, конечное состояние (stop) и символы возврата из процедуры (return). Назовём все эти элементы узлами конечного автомата.
Рассмотрим множество узлов N конечного автомата. Назовём узел s
N входным для множества узлов N, если существует переход t (a->s; sig; act) и a 
N. Назовём узел b N выходным для множества узлов N, если существует переход t (s->b; sig; act) и s N.
Сформулируем необходимые условия для выделения части конечного автомата в метод:
Множество узлов N, не содержащее stop, и все переходы между ними можно перенести в отдельный метод, если для множества узлов N существует ровно один входной узел и не более одного выходного узла.
Для поиска частей автомата, которые можно перенести в отдельный метод, должно использоваться то же самое условие. Необходимо искать множества узлов с одним входным и одним выходным узлом. На приведён пример автомата, удовлетворяющего заданному условию. Данное условие не ограничивает количество переходов, по которым можно попасть во входной или выходной узел, и, как видно на рисунке, для входного узла decision (x) и для выходного узла Q существует по два перехода, ведущие в них.
Все узлы из выделенного множества, decision (x), s1, s2, s3 перемещаются в новый метод Proc (). Переходы, ведущие во входное состояние, после трансформации напрямую направляются в выходное состояние Q. К действиям, выполняемым в этих переходах, добавляется вызов метода Proc () (Рис. 9).
Рис. 9.Результат трансформации
Переходы, ведущие в выходное состояние, переносятся в метод и направляются в символ возврата из процедуры ().
В основе необходимого свойства для выделения части конечного автомата в метод лежит следующая идея. Состояния, переносимые в выделяемый метод, перестают принадлежать исходному автомату, и, следовательно, некорректны команды перехода, которые приводят из состояний исходного автомата в состояния, перенесенные в выделенный автомат. Такие команды перехода (смены состояния) должны быть заменены командами вызова выделяемого метода. Однако у автомата, реализующего метод, может быть только одна входная точка, поэтому все такие команды должны осуществлять переход в одно и то же состояние. Аналогичные рассуждения касаются и обратных переходов из состояний выделенного метода в состояния исходного автомата.
Трансформации «выделение метода для конечного автомата», описанные в предыдущих двух параграфах, являются частными случаями трансформации общего вида, базирующейся на необходимом условии.В случае, когда входной узел совпадает с выходным, получаем возвратную часть конечного автомата, которую можно выделить в метод. Последовательные части конечного автомата, очевидно, также удовлетворяют необходимому условию для выделения части конечного автомата в метод.
Существуют и другие частные случаи приведённого необходимого условия:
- Множество узлов не имеет ни одного выходного узла (и по необходимому условию не содержит stop), то есть возврат из созданного метода невозможен. Это значит, что в конечном автомате найден бесконечный цикл, который, возможно, представляет собой «серверную составляющую» исходного автомата.
- В случае, когда выходной узел - это stop, выделенный метод выполняет действия, после которых автомат завершает свою работу, так что, возможно, новый метод является неким аналогом деструктора в объектно-ориентированном программировании.
