Реферат
ВВЕДЕНИЕ 5
1 Конечные автоматы и их композиции 6
1.1 Определение конечного автомата 6
1.2 Классификация композиций 8
1.3 Построение бинарной параллельной композиции автоматов 10
1.4 Применение инструмента BALM-II для формирования команд бинарной
параллельной композиции 14
1.5 Инструмент FSMComposition 15
2 Этапы автоматического формирования BALM-II скрипта 17
2.1 Графический редактор FSMComposition и внутренняя структура 17
2.2 Разработка алгоритма формирования BALM-II скрипта 17
2.3 Формирование команд с параметрами 18
3 Выбор способа внешнего представления 20
3.1 Текстовый формат JSON 20
3.2 Язык разметки XML 21
3.3 Описание структуры автоматной композиции при помощи XML 22
3.4 Предлагаемые XML теги 23
3.5 Задание схемы XML документа с помощью XSD файла 24
ЗАКЛЮЧЕНИЕ 25
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 26
ПРИЛОЖЕНИЕ А Внутренняя структура 27
ПРИЛОЖЕНИЕ B Программа по формированию BALM-II скрипта 29
ПРИЛОЖЕНИЕ С XML теги 33
ПРИЛОЖЕНИЕ D XSD представление 34
В настоящее время многие современные системы, как программные, так и аппаратные, ориентированы на совместное функционирование. Например, это вебсервисы, телекоммуникационные протоколы и т.д. Для проверки совместной работы таких систем часто требуется формальное описание их взаимодействия. И если отдельную систему можно описать при помощи модели конечного автомата [1,2], то при некоторых ограничениях, взаимодействие таких систем также может быть описано автоматом в результате построения соответствующей композиции [2]. Для формального описание взаимодействия нескольких систем часто рассматривается, как основной шаг умение описать поведение двух систем - так называемая бинарная композиция, причем чаще всего актуален режим диалога (параллельная композиция). Так как в большинстве случаев программные реализации работают именно в режиме диалога. Для автоматического построения бинарной параллельной композиции автоматов можно использовать инструмент BALM-II [4].
Этот инструмент имеет ограничение на число компонент, кроме того, в файлах, задающих композируемые автоматы, жестко определяются каналы композиции, что не удобно для пользователя.
Для усовершенствования процесса построения параллельной композиции автоматов, а также в дальнейшем для построения модели многокомпонентных систем было решено разработать автоматизированную систему.
Таким образом, можно сформировать цель данной бакалаврской работы - автоматизировать построение композиции по описанию структуры работы компонент (в случае, если поведение каждого компонента задано конечным автоматом).
Для выполнения поставленной цели в рамках данной работы необходимо было решить следующие задачи:
1. Изучить литературу по конечным автоматам
2. Рассмотреть взаимодействие автоматов между собой
3. Написать алгоритм по формированию BALM-II скрипта на основе внутреннего представления структуры композиции
4. Программно реализовать алгоритм и отладить его
5. Изучить языки разметки и текстовые форматы обмена данными для того, чтобы выбрать подходящий вариант внешнего задания структуры композиции
6. Предложить способ/ формат внешнего описания композиции автоматов
Многокомпонентные системы (программные реализации), такие как веб-сервисы, телекоммуникационные протоколы ориентированы на совместное взаимодействие. Основным шагом для описание таких систем, является умение описать поведения их взаимодействия, т.е. умение построить соответствующую композицию.
Данная бакалаврская работа была направлена на усовершенствование процесса построения модели многокомпонентных систем. Целью являлось автоматизировать построение многокомпонентных систем, если поведение каждой компоненты задано конечным автоматом. Работа была посвящена созданию набора команд, которые формируются из алгоритма по формированию BALM-II скрипта на основе внутренней структуры автоматной композиции, которая в дальнейшем позволит расширить возможности инструмента BALM-II для автоматизированного построения композиции.
В рамках данной работы был изучен материал по теории конечных автоматов, также было рассмотрено взаимодействие автоматов между собой. При описании композиции, а также при описании модели многокомпонентных систем использовалась модель конечного автомата. Для построения бинарной параллельной композиции существует инструмент BALM-II, но с помощью данного инструмента, команды для построения композиции формируются вручную. В связи с этим, был разработан скрипт, который автоматически формирует команды и подает на инструмент BALM-II. Был разработан алгоритм автоматического построения бинарной параллельной композиции конечных автоматов, который был программно реализован и протестирован.
Для формирования внешнего представления структуры композиции, было проанализировано два формата описания структуры композиции. Был изучен синтаксис языка разметки XML. Также был разработан и предложен набор XML тегов, позволяющих задавать структуру описания параллельной композиции автоматов. С помощью набора XML-тегов был рассмотрен ряд примеров описания структуры.
Таким образом, с помощью внутреннего и внешнего представления, полуавтоматическое построение параллельной композиции конечных автоматов будет являться полностью автоматическим, т.е. пользователю не нужно будет формировать команды в ручном режиме на основе визуального анализа структуры композиции.
В заключении, по результату данной работы были напечатаны тезисы [6] и представлен доклад на международной конференции ICAM’18 и доклад на конференции СНИИ-2019.
В дальнейшем планируется продолжить данную работу. Распространить данный подход на другие виды композиции конечных автоматов, а также рассмотреть задачу автоматизации построения композиций современных конечно автоматных моделей, в том числе, временных и расширенных автоматов.
