Моделирование дискретно-событийных систем средствами графического языка состояний и переходов конечных автоматов

Федеральное государственное бюджетное образовательное учреждение

высшего образования «Московский государственный университет

имени М.В.Ломоносова»

Факультет вычислительной математики и кибернетики

Фонд содействия развитию интернет-медиа, ИТ-образования, человеческого потенциала «Лига интернет-медиа»

_____________________________________________________________________________

В. А. Сухомлин, Д. А. Гапанович, В. М. Дубков, М. А. Князев

Моделирование дискретно-событийных систем средствами графического языка состояний и переходов конечных автоматов

Учебник для вузов

Рекомендовано ФУМО по укрупненной группе специальностей и направлений подготовки 02.00.00 Компьютерные и информационные науки в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям подготовки: «Фундаментальная информатика и информационные технологии», «Математическое обеспечение и администрирование информационных систем», «Математика и компьютерные науки»

Москва – 2026

УДК 519.713(075.8)

ББК 22.182.3я73

М 74

Р е ц е н з е н т ы:

М.А. Посыпкин – член-корр. РАН, д.ф.-м.н., профессор, директор ФИЦ ИУ РАН;

Д.Е. Намиот – д.т.н., в.н.с. МГУ имени М.В.Ломоносова

Сухомлин В. А., Гапанович Д. А., Дубков В. М., Князев М. А.

М 74

Моделирование дискретно-событийных систем средствами графического языка состояний и переходов конечных автоматов : учебник / В.А. Сухомлин, Д.А. Гапанович, В.М. Дубков, М.А. Князев. – Москва : МГУ; Фонд «Лига интернет-медиа», 2026. – 100 c.

ISBN 978-5-521-25037-0

https://doi.org/10.25559/978-5-521-25037-0

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

Приводится сравнение языка DLAA с известными графическими языками такими, как диаграммы Мура, диаграммы состояний Харела, диаграммы конечных автоматов языков SysML и UML, методология А.А. Шалыто, формализм DEVS.

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

Пособие предназначено для освоение студентами методов моделирования динамических систем дискретно-событийного класса при выполнении лабораторных, практических и проектных работ по курсу «Системная инженерия».

Ключевые слова: язык графического моделирования, DLAA, теория автоматов, дискретно-событийное моделирование, конечные автоматы, автоматное моделирование, диаграммы переходов и состояний, онтология, онтологическая схема, онтологическое моделирование, онтологическая платформа.

Авторы благодарят команду компании .Time and Space. – лично управляющего партнёра Юрия Ивановича Волокитина, директора по развитию Дмитрия Юрьевича Волокитина и ведущего инженера-онтолога Дмитрия Вячеславовича Волокитина, а также всех разработчиков платформы OSA – за создание инструментальной среды, на которой основана настоящая работа.

УДК 519.713(075.8)

ББК 22.182.3я73

ISBN 978-5-521-25037-0 © Сухомлин В. А., Гапанович Д. А., Дубков В. М., Князев М. А., 2026

© Фонд «Лига интернет-медиа», 2026

Оглавление

Введение 5

Глава 1. Анализ наиболее известных визуальных средств описания поведенческих аспектов систем на основе конечных автоматов 7

1.1. Автоматы Мили и Мура 7

1.2. Абстрактная модель дискретной системы Уаймора 9

1.3. Автоматы Харела 10

1.4. Автоматное программирование А.А. Шалыто 10

1.5. Конечные автоматы в языках SysML и UML 11

1.6. DEVS — формализм для моделирования сложных динамических систем с использованием абстракции дискретных событий 12

Выводы 15

Глава 2. Определение языка DLAA, требований к языку, базовые операции языкового ядра 16

2.1. Ядро языка 16

2.2. Формализм спецификации конечного автомата языка DLAA 17

Глава 3. Графическая форма языка DLAA 22

Глава 4. Расширение языка DLAA функциональной семантикой 26

Глава 5. Структурирование состояний диаграмм 29

Глава 6. Операционная семантика языка DLAA. Абстрактный симулятор 32

6.1 Модель времени 32

6.2 Абстрактный симулятор языка DLAA 34

Глава 7. Погружение концептуальной модели языка DLAA в среду онтологической платформы 43

7.1. Платформа OSA 43

7.2. Онтологическая схема языка DLAA 44

Глава 8. Инструментальные средства автоматизации создания цифровых моделей на основе языка DLAA 48

8.1 Особенности реализации графического конструктора диаграмм языка DLAA 49

8.2 Конвертор онтологического образа модели в семантически эквивалентные конструкции базового языка 50

8.3 Особенности реализации симулятора 52

Список литературы 54

Приложение A 56

Синтаксис метаязыка AADL 56

Приложение Б 59

Пример использования языка для моделирования системы автоматов 59

Приложение В 75

Пример Кнута, модель функционирования лифта 75

Введение

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

Одной из центральных парадигм цифровизации производства служит концепция цифровых двойников (Digital Twin) или сокращенно ЦД, на основе которой реализуется современный подход к созданию и эксплуатации сложных объектов (физических активов, таких, как: технические системы, производственные процессы, предприятия, цеха, машины и т.п.). Данный подход предполагает использование полномасштабных цифровых моделей физических активов, которые, во-первых, обладают высокой степенью сходства со свойствами и поведением физического актива и, во-вторых, обладают зеркальной информационной взаимосвязью в реальном времени с активом, превращающую последний в целостную кибер-физическую систему (Cyber-Physical System - CPS) с возможностью управления ею, как на физическом, так и виртуальном уровнях [1, 2].

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

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

Поддержка структурированного подхода и модельности в разработке ЦД и возможности комплексирования двойников активов в двойники систем.

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

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

В первой главе приводится анализ наиболее известных средств описания поведенческих аспектов систем на основе конечных автоматов, включая: классические диаграммы Мура, абстрактная модель дискретной системы Уаймора, диаграммы состояний (Statecharts) Д. Харела, - автоматное программирование А.А. Шалыто, конечные автоматы в языках SysML и UML, DEVS (Discrete-Event Modelling and Simulation) – наиболее мощный формализм для моделирования сложных динамических систем с использованием абстракции дискретных событий.

Во второй главе описаны понятия и возможности базового языка DLAA, расширяющего класс автоматов Мили и названный классом автоматов Мили*.

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

В четвертой главе рассмотрена следующая очередь расширения языка введением еще двух механизмов это механизма структурирования диаграмм на основе введенной в алгебре DTA (Digital Twin Algebra) операции рекурсивного вызова автоматов [3], и механизма прерываний, предназначенного для прерывания выполняемой в рамках состояния автомата работы и перехода на альтернативную ветвь работы автомата.

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

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

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

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

Приложение A. Синтаксис метаязыка AADL.

Приложение Б. Пример использования языка для моделирования системы автоматов.

Приложение В. Пример. Модель функционирования лифта.

Приложение Г. Инструкция по применению (на примере Приложения В).

Приложение Д.

Глава 1. Анализ наиболее известных визуальных средств описания поведенческих аспектов систем на основе конечных автоматов

1.1. Автоматы Мили и Мура

Классическими видами конечных автоматов являются автоматы Мили и Мура [5, 6]. Конфигурация для обоих видов автоматов (с начальным состоянием q0) одна и та же и имеет следующий вид:

M =

где:

A – входной алфавит – непустое конечное множество входных символов (входных событий автомата, например, сигналов от сенсоров),

B – выходной алфавит – непустое конечное множество выходных символов (например, продуцируемых автоматом событий или сигналов),

Q – множество состояний автомата – непустое конечное множество символов состояний автомата (его память),

δ – функции переходов автомата – однозначное отображение вида: Q×A→Q

λ – функцией выходов автомата – отображение вида: Q×A→B

q0 - начальное состояние автомата q0.

Особенностью автомата Мили является то, что его функция выходов представляет собой отображение вида: Q×A→B, т.е. выход автомата зависит как от текущего состояния автомата, так и от его текущего входа (входного вектора). В конечных автоматах Мура выходные данные системы, в отличие от автоматов Мили, связаны только с состояниями, т.е. функцией выходов автомата λ является отображением вида: Q→B.

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

Автоматы Мили и Мура можно считать эквивалентными, так как показана осуществимость преобразований между конечными автоматами Мура и автоматами Мили и наоборот [7].

Далее будем предполагать, что конечные автоматы, с которыми мы будем иметь дело, являются полными и детерминированными. Детерминированные автоматы – это автоматы, для которых состояние δ(q, a) однозначно определяется парой (q, a) ∈ Q × A, т.е. функция переходов δ(q, a)= q действительно является функцией.

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

(q, a) ∈ Q × A .

Конечные автоматы имеют наглядную форму представления в виде помеченных графов, называемых диаграммами Мура. Такими графами или диаграммами Мура, представляющими конечные автоматы, будем называть абстрактные сущности, состоящие из конечного множества вершин-состояний автомата Q, и конечного множества направленных дуг E, соединяющих две вершины (начальную и конечную). В таких графах будут допускаться дуги, имеющие одинаковые начала и концы, называемые также параллельными. Разметка графов осуществляется с помощью отображения E→A×B, где каждой дуге ставится в соответствие пара - входной символ a∈A и выходной символ b∈B. Таким образом, переход из состояния q в состояние q′, вызванный входной буквой a, изображается дугой с началом q, концом q′ и меткой «a», при этом при переходе по дуге осуществляется вывод выходного символа b= λ(q, a).

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

Рассмотрим автомат M = <A, B, Q, δ, λ, q0>, у которого:

A={0, 1},

B={0, 1},

Q={q0, q1, q2},

{δ(q0, 0)=q1, δ(q0, 1)=q1, δ(q1, 0)=q2, δ(q1, 1)=q2, δ(q2, 0)=q0, δ(q2, 1)=q0},

{λ(q0, 0)=0, λ(q0, 1)=1, λ(q1, 0)=0, λ(q0, 1)=1, λ(q2, 0)=1, λ(q2, 1)=0,)}.

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

На рис. 1 представлен граф этого автомата, в котором параллельные дуги заменены единственными дугами, помеченных списком меток, составленным из меток параллельных дуг.

Рисунок 1. Диаграмма Мура конечного автомата, инвертирующего каждый третий символ входного потока

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

1.2. Абстрактная модель дискретной системы Уаймора

К наиболее строгим с математической точки зрения подходам использования математической структуры для описания дискретных систем следует отнести исследования Уаймора [8]. В основе подхода Уаймора лежит определение модели дискретной системы, и концепции рецепта связи (Coupling Recipe) – аналога блок-схемы системы, связывающей отношениями элементы системы.

В рассматриваемой работе Уаймор определяет модель дискретной системы как пятерку:

𝑍 = {𝑆𝑍, 𝐼𝑍, 𝑂𝑍, 𝑁𝑍, 𝑅𝑍}, где:

Z — имя системы

SZ — множество ее состояний

IZ — множество ее входов

OZ — набор ее выходных данных

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

RZ — функция считывания (вывода), которая определяет выходные данные для каждого состояния.

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

Пример, поясняющий применение механизма рецепта связывания [9], исходные данные и постановка задачи примера приведены на рис. 1, где требуется построить результирующую систему Z* = RES(K) при соединении K систем Zi для i = {1-4} и необходимо указать множество, определяющее связь K. Пример графического изображения входных/выходных связей дискретных систем Z1, Z2, Z3, Z4 и как результат связанная система Z* = RES(K), приведены на рис. 2.

Рисунок 2. Пример связанной системы [9]

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