Scientific FigureScientific Figure
ДКА, НКА, автоматы Мура и Мили, UML

Диаграмма состояний онлайн для конечных автоматов и UML

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

Заголовок
Переходы, по одному на строку

Запишите переход как q0 -a-> q1, q0 -> q1 : a или тремя колонками из таблицы. Добавьте строки start: и accept: (ключевые слова пишутся по-английски); входы, идущие по одной стрелке, объединяются в «0, 1». Конструктор диаграмм состояний считает начальным первое состояние, если строка start: не называет другое.

Состояний: 3, переходов: 6, входной алфавит {0, 1}. У каждого состояния ровно один переход по каждому символу, так что это полный ДКА.

Направление
Цвета
Скачать

Конструктор диаграмм состояний раскладывает автомат прямо в этой вкладке браузера: без аккаунта, без загрузки на сервер, файл остаётся вашим.

ДКА для двоичных строк, оканчивающихся на 01 (диаграмма состояний)q0 переходит в q1 по 0; q1 переходит в q2 по 1; q2 переходит в q1 по 0; q2 переходит в q0 по 1; q0 переходит в q0 по 1; q1 переходит в q1 по 0ДКА для двоичных строк, оканчивающихсяна 01старт010110q0q1q2scientificfigure.com
Нужен вариант от руки на доске, иллюстрированный светофор или торговый автомат для слайда или рисунок для проектной документации?
Таблица переходов→ начальное состояние, * допускающее состояние
СостояниеВход 0Вход 1
→ q0q1q0
q1q1q2
* q2q1q0

Примеры диаграмм состояний

Восемь примеров диаграмм состояний от ИИ-генератора конструктора диаграмм состояний: торговый автомат, состояния соединения TCP, ДКА, цепь Маркова и четыре варианта оформления. Каждый пример — настоящая картинка с запросом, по которому она нарисована; выберите карточку, чтобы загрузить запрос.

Торговый автомат

UML-диаграмма состояний торгового автомата с подписью событие [условие] / действие на каждой стрелке, от ИИ-генератора диаграмм состояний.

Соединение TCP

Диаграмма состояний соединения TCP по RFC 9293 от конструктора диаграмм состояний: одиннадцать состояний от CLOSED до TIME-WAIT со всеми событиями и действиями.

ДКА: делимость на 3

ДКА, допускающий двоичные числа, кратные 3, со стрелкой в начальное состояние и двойным кругом допускающего, от конструктора диаграмм состояний.

Цепь Маркова: погода

Цепь Маркова для погоды по дням с вероятностью перехода на каждой стрелке, от ИИ-генератора диаграмм состояний.

Автомат Мура для 101

Рисунок из учебника от ИИ-генератора диаграмм состояний: автомат Мура, который выдаёт 1 после входа 101, выходы записаны внутри состояний.

Пешеходный переход

Набросок на доске от ИИ-генератора диаграмм состояний: пешеходный переход с переходами по таймеру и нажатием кнопки, нарисован маркером.

Жизненный цикл онлайн-заказа

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

Контроллер лифта

Диаграмма состояний на тёмном слайде: контроллер лифта со сторожевыми условиями на переходах, готовый для доклада или лекции.

Что такое диаграмма состояний?

Диаграмма состояний — это рисунок состояний, в которых может находиться система, и переходов между ними: каждое состояние — вершина, а каждая стрелка — переход, подписанный входом или событием, которое его вызывает. Тот же рисунок называют диаграммой переходов, графом конечного автомата, диаграммой конечного автомата (state machine diagram, название в UML) или стейтчартом, по расширенной форме Дэвида Харела, на которой основаны машины состояний UML.

Что умеет конструктор диаграмм состояний

  • Конструктор диаграмм состояний читает по одному переходу на строку: q0 -a-> q1 из конспекта, A --> B : событие из Mermaid или три колонки из таблицы.
  • Нотация автоматов: стрелка из ниоткуда в начальное состояние, допускающие состояния двойными кругами, петли и входы на общей стрелке, объединённые в «0, 1».
  • Нотация UML: состояния скруглёнными прямоугольниками, маленький залитый круг для начального псевдосостояния, кольцо вокруг залитой точки для конечного состояния, стрелки с подписью событие [условие] / действие.
  • Конструктор диаграмм состояний проверяет каждую раскладку перед рисованием: состояния не перекрываются, и ни одна подпись не лежит на состоянии, на другой подписи или на чужой стрелке.
  • Таблица переходов строится из того же списка: строка на состояние для ДКА, множества следующих состояний для НКА, следующее состояние / выход для автомата Мили, матрица переходов для цепи Маркова.
  • Строка состояния конструктора диаграмм состояний сообщает, ДКА это или НКА, перечисляет недостающие переходы и недостижимые состояния и проверяет, что вероятности цепи Маркова в сумме дают 1.
  • Конструктор диаграмм состояний скачивает файлы PNG, SVG и PDF в цвете или чёрно-белые, бесплатно и без регистрации.

Нотация диаграммы состояний в UML и в теории автоматов

Под одним названием живут две нотации, и на одной диаграмме состояний нужно держаться одной из них. В проектировании ПО используют UML-машину состояний: состояние — скруглённый прямоугольник, а стрелка несёт подпись событие [условие] / действие. В курсах теории автоматов и цифровой схемотехники состояния рисуют кругами, начальное отмечают стрелкой из ниоткуда, а допускающие двойным кругом. Конструктор диаграмм состояний рисует обе из одного списка переходов.

Конечный автомат (теория автоматов)
СимволНазваниеЧто означает
Начальное состояниеНа него указывает стрелка из ниоткуда, часто с подписью «старт». У ДКА оно ровно одно.
СостояниеКруг с именем состояния, например q0. В автоматах Мура выход пишут после косой черты, S3/1.
Допускающее (заключительное) состояниеВторой круг внутри первого. У автомата может быть несколько допускающих состояний или ни одного.
ПетляПереход, который выходит из состояния и возвращается в него же, подписанный своими входами.
0, 1Подпись переходаВходные символы, по которым идёт стрелка, через запятую; ε обозначает переход без чтения входа, такой бывает только у НКА.
1/0Выход автомата Миливход/выход на стрелке, например 1/0: выход принадлежит переходу, а не состоянию.
Нотация автоматов: начальное состояние чёт одновременно допускающее, поэтому у него есть и стрелка «старт», и двойной круг. Конструктор диаграмм состояний разложил его из шести строк.чёт переходит в нечет по 0; нечет переходит в чёт по 0; чёт переходит в чёт по 1; нечет переходит в нечет по 1ДКА для чётного числа нулейстарт0011чётнечет
Нотация автоматов: начальное состояние чёт одновременно допускающее, поэтому у него есть и стрелка «старт», и двойной круг. Конструктор диаграмм состояний разложил его из шести строк.
UML-машина состояний (UML 2.5.1)
СимволНазваниеЧто означает
Начальное псевдосостояниеМаленький залитый круг. У его единственного исходящего перехода нет ни события, ни условия.
СостояниеПрямоугольник со скруглёнными углами и именем состояния; в дополнительном отделении можно перечислить поведение entry /, do / и exit /.
e [g] / aПереходсобытие [условие] / действие, каждая часть необязательна: монета / открыть, выбор товара [сумма ≥ цена] / выдать товар.
Конечное состояниеКольцо вокруг маленького залитого круга: область завершила работу.
Псевдосостояние выбораРомб, исходящие переходы которого несут условия, выбирающие ветку.
Нотация UML: начальное псевдосостояние указывает на Закрыт, у обоих состояний есть петли, а отключение ведёт в конечное состояние. Вставлено в конструктор диаграмм состояний строками Mermaid.Закрыт переходит в Открыт по монета / открыть; Открыт переходит в Закрыт по толчок / закрыть; Закрыт переходит в по отключение; Закрыт переходит в Закрыт по толчок / тревога; Открыт переходит в Открыт по монета / спасибоТурникет с монетоприёмникоммонета / открытьтолчок / закрытьотключениетолчок / тревогамонета / спасибоЗакрытОткрыт
Нотация UML: начальное псевдосостояние указывает на Закрыт, у обоих состояний есть петли, а отключение ведёт в конечное состояние. Вставлено в конструктор диаграмм состояний строками Mermaid.

Как читать таблицу переходов

Таблица переходов — это диаграмма состояний, записанная сеткой: строка на каждое состояние, столбец на каждый вход, а в ячейке состояние, в которое переходит автомат. Стрелка → отмечает начальное состояние, а * допускающие. Таблица и рисунок содержат одну и ту же информацию, поэтому в задачах просят построить одно по другому; конструктор диаграмм состояний строит таблицу под каждым рисунком.

ДКА для двоичных чисел, кратных 3, нарисованный конструктором диаграмм состояний. Состояние ri означает, что прочитанные биты дают остаток i.r0 переходит в r1 по 1; r1 переходит в r2 по 0; r1 переходит в r0 по 1; r2 переходит в r1 по 0; r0 переходит в r0 по 0; r2 переходит в r2 по 1ДКА для двоичных чисел, кратных 3старт101001r0r1r2
ДКА для двоичных чисел, кратных 3, нарисованный конструктором диаграмм состояний. Состояние ri означает, что прочитанные биты дают остаток i.
СостояниеВход 0Вход 1
→ * r0r0r1
r1r2r0
r2r1r2
  • Читайте строку как «из этого состояния по этому входу перейти в»: r1 по 0 переходит в r2, потому что прочитанные биты, умноженные на два, дают остаток 2.
  • У ДКА в каждой ячейке ровно одно состояние. Конструктор диаграмм состояний показывает отсутствующий переход пустой ячейкой (—): такой ДКА частичный, и в учебниках его дополняют «мёртвым» состоянием.
  • У НКА в ячейке множество состояний, {q0, q1}, или ∅, а столбец ε перечисляет переходы, не читающие вход.
  • В таблице автомата Мили в каждой ячейке следующее состояние / выход; таблица цепи Маркова — матрица переходов, сумма каждой строки которой равна 1.

Диаграммы состояний автоматов Мура и Мили

Выход автомата Мура зависит только от состояния, поэтому его пишут внутри состояния; выход автомата Мили зависит от состояния и входа, поэтому его пишут на стрелке в виде вход/выход. Обе диаграммы ниже распознают последовательность 101 с перекрытием. Автомату Мили нужно три состояния, автомату Мура четыре, потому что Муру нужно отдельное состояние «только что видел 101». Конструктор диаграмм состояний нарисовал их из девяти и семи строк переходов.

Автомат Мура в конструкторе диаграмм состояний: S3/1 — единственное состояние с выходом 1.S0/0 переходит в S1/0 по 1; S1/0 переходит в S2/0 по 0; S2/0 переходит в S3/1 по 1; S3/1 переходит в S2/0 по 0; S2/0 переходит в S0/0 по 0; S3/1 переходит в S1/0 по 1; S0/0 переходит в S0/0 по 0; S1/0 переходит в S1/0 по 1Автомат Мура, распознающий 101 (с перекрытием)старт10100101S0/0S1/0S2/0S3/1
Автомат Мура в конструкторе диаграмм состояний: S3/1 — единственное состояние с выходом 1.
Автомат Мили в конструкторе диаграмм состояний: стрелка S2 → S1 с подписью 1/1 — единственный переход, который выдаёт 1.S0 переходит в S1 по 1/0; S1 переходит в S2 по 0/0; S2 переходит в S1 по 1/1; S2 переходит в S0 по 0/0; S0 переходит в S0 по 0/0; S1 переходит в S1 по 1/0Автомат Мили, распознающий 101 (сперекрытием)старт1/00/01/10/00/01/0S0S1S2
Автомат Мили в конструкторе диаграмм состояний: стрелка S2 → S1 с подписью 1/1 — единственный переход, который выдаёт 1.
Автомат МураАвтомат Мили
Выход зависит отТолько текущего состоянияТекущего состояния и входа
Где записан выходВнутри состояния: S3/1На переходе: 1/1
Состояний для распознавания 10143
Когда меняется выходТолько при входе в новое состояниеСразу при изменении входа
В таблице переходовОдин выход на строку, рядом с состояниемследующее состояние / выход в каждой ячейке

Диаграммы состояний, которые рисуют студенты и инженеры

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

Диаграмма состояний соединения TCP

RFC 9293, действующий стандарт TCP, сводит соединение в рисунок 5: одиннадцать состояний от CLOSED через LISTEN, SYN-SENT и ESTAB до TIME-WAIT, каждая стрелка подписана событием и действием, которое оно вызывает. Сам RFC предупреждает, что диаграмма «лишь сводка и не должна восприниматься как полная спецификация». Конструктор диаграмм состояний нарисовал этот рисунок по двадцати переходам из того рисунка, сверху вниз, как в оригинале; имена состояний и событий оставлены, как в RFC.

Диаграмма состояний соединения TCP по RFC 9293, рис. 5, нарисованная конструктором диаграмм состояний.CLOSE-WAIT переходит в LAST-ACK по CLOSE / snd FIN; SYN-RCVD переходит в FIN-WAIT-1 по CLOSE / snd FIN; LISTEN переходит в SYN-RCVD по rcv SYN / snd SYN,ACK; SYN-RCVD переходит в LISTEN по rcv RST; SYN-SENT переходит в ESTAB по rcv SYN,ACK / snd ACK; FIN-WAIT-1 переходит в FIN-WAIT-2 по rcv ACK of FIN; FIN-WAIT-1 переходит в CLOSING по rcv FIN / snd ACK; FIN-WAIT-2 переходит в TIME-WAIT по rcv FIN / snd ACK; CLOSING переходит в TIME-WAIT по rcv ACK of FIN; ESTAB переходит в CLOSE-WAIT по rcv FIN / snd ACK; CLOSED переходит в LISTEN по passive OPEN / create TCB; CLOSED переходит в SYN-SENT по active OPEN / create TCB, snd SYN; LISTEN переходит в CLOSED по CLOSE / delete TCB; SYN-SENT переходит в CLOSED по CLOSE / delete TCB; SYN-SENT переходит в SYN-RCVD по rcv SYN / snd SYN,ACK; ESTAB переходит в FIN-WAIT-1 по CLOSE / snd FIN; LISTEN переходит в SYN-SENT по SEND / snd SYN; SYN-RCVD переходит в ESTAB по rcv ACK of SYN; LAST-ACK переходит в CLOSED по rcv ACK of FIN; TIME-WAIT переходит в CLOSED по Timeout=2MSL / delete TCBДиаграмма состояний соединения TCP (RFC 9293, рис. 5)CLOSE / snd FINCLOSE / snd FINrcv SYN/ snd SYN,ACKrcv RSTrcv SYN,ACK/ snd ACKrcv ACK of FINrcv FIN / snd ACKrcv FIN / snd ACKrcv ACK of FINrcv FIN / snd ACKpassive OPEN/ create TCBactive OPEN/ create TCB, sndSYNCLOSE/ delete TCBCLOSE/ delete TCBrcv SYN/ snd SYN,ACKCLOSE / snd FINSEND / snd SYNrcv ACK of SYNrcv ACK of FINTimeout=2MSL/ delete TCBCLOSEDLISTENSYN-SENTSYN-RCVDESTABFIN-WAIT-1CLOSE-WAITFIN-WAIT-2CLOSINGTIME-WAITLAST-ACK
Диаграмма состояний соединения TCP по RFC 9293, рис. 5, нарисованная конструктором диаграмм состояний.

Диаграмма состояний ДКА

ДКА — простейший конечный автомат, и в упражнениях по теории автоматов просят построить автомат, допускающий язык, например двоичные числа, кратные 3. Три состояния хранят остаток, r0 одновременно начальное и допускающее, и у каждого состояния одна стрелка для 0 и одна для 1.

Диаграмма состояний НКА с ε-переходами

У НКА может быть несколько стрелок по одному символу и стрелки с подписью ε. Этот автомат допускает a* ∪ b*: два ε-перехода из q0 выбирают ветку, а q1 и q2 оба допускающие.

Диаграмма состояний JK-триггера

Два состояния, Q=0 и Q=1. Из Q=0 входы JK = 0X оставляют Q равным 0, а 1X устанавливают его; из Q=1 X0 сохраняют, а X1 сбрасывают. X означает безразличное значение, поэтому четыре пары входов помещаются на двух стрелках у каждого состояния.

Нарисовать сам триггер в конструкторе электрических схем

Диаграмма состояний счётчика

2-битный реверсивный счётчик обходит 00, 01, 10 и 11 по кольцу: вход 1 делает шаг вперёд, вход 0 шаг назад, поэтому у каждой пары соседей две стрелки.

Диаграмма состояний светофора

Контроллер с таймером в нотации UML: через 30 с красный сменяется зелёным, через 25 с зелёный жёлтым, через 5 с жёлтый красным. after — ключевое слово UML для временного события.

Диаграмма состояний торгового автомата

Классическое упражнение по проектированию ПО: ожидание, приём монет и выдача, со сторожевым условием [сумма ≥ цена] на стрелке выбора и действиями после косой черты.

Машина состояний жизненного цикла заказа

У бизнес-объектов тоже есть состояния. Заказ переходит из ожидания оплаты в оплаченный, отправленный и доставленный или заканчивается отменой или возвратом; каждое завершающее состояние ведёт в конечное состояние UML.

Диаграмма состояний цепи Маркова

В цепи Маркова каждая стрелка несёт вероятность, а стрелки, выходящие из состояния, в сумме дают 1. Таблица становится матрицей переходов, и конструктор отмечает любую строку, сумма которой не равна 1.

Проследить два шага деревом вероятностей

Как нарисовать диаграмму состояний

  1. 1

    Перечислите состояния и начало

    Назовите каждое состояние, в котором система может ждать, прежде чем что-то вводить в конструктор диаграмм состояний. В нотации автоматов одно из них начальное; в UML автомат стартует из начального псевдосостояния.

  2. 2

    Введите переходы в конструктор диаграмм состояний

    Одна строка на переход: состояние, из которого он выходит, вход или событие, состояние, в которое он ведёт. Диаграмма переходов перерисовывается по мере ввода, а переход обратно в то же состояние становится петлёй.

  3. 3

    Отметьте допускающие или конечные состояния

    Добавьте accept: q2 для автомата или Состояние --> [*] для конечного состояния UML. Строка состояния конструктора диаграмм состояний называет недостающие переходы и недостижимые состояния.

  4. 4

    Сверьте таблицу и скачайте диаграмму состояний

    Сравните таблицу переходов со своим ответом, при необходимости переключитесь на «сверху вниз» или чёрно-белый вариант и сохраните рисунок из конструктора диаграмм состояний в PNG, SVG или PDF.

Вопросы о диаграмме состояний

Чем диаграмма состояний отличается от диаграммы конечного автомата в UML?

+

Это один и тот же вид рисунка; state machine diagram, диаграмма конечного автомата, — название, принятое в UML. Диаграмма состояний и диаграмма переходов — общие термины теории автоматов и цифровой логики. Стейтчарт — расширение Дэвида Харела с вложенными и параллельными состояниями, и спецификация UML 2.5.1 говорит, что её машины состояний основаны на объектно-ориентированном варианте стейтчартов Харела. Конструктор диаграмм состояний рисует обычные машины состояний в любой из нотаций; вложенные состояния не рисуются.

Как отметить начальное и допускающие состояния?

+

В конструкторе диаграмм состояний добавьте строку start: и строку accept:, например start: q0 и accept: q2, q3. Начальное состояние получит стрелку из ниоткуда, а каждое допускающее двойной круг. Без строки start: начальным считается первое написанное состояние. В нотации UML пишите [*] --> Состояние для начального перехода и Состояние --> [*] для перехода в конечное состояние.

Как отличить ДКА от НКА по диаграмме состояний?

+

На диаграмме состояний ДКА из каждого состояния выходит ровно одна стрелка на каждый входной символ и нет подписей ε; всё остальное — НКА. У НКА может быть две стрелки по одному символу, ни одной или ε-переходы. Строка состояния конструктора диаграмм состояний сообщает, что вы нарисовали, и называет состояние и символ, из-за которых автомат недетерминирован, или переходы, которых не хватает частичному ДКА.

Как превратить диаграмму состояний в таблицу переходов?

+

Запишите строку на каждое состояние и столбец на каждый входной символ и поставьте в ячейку следующее состояние; конструктор диаграмм состояний строит такую таблицу под рисунком. Начальное состояние отмечают →, допускающие *. У НКА в ячейке множество состояний, у автомата Мили следующее состояние / выход. Скопируйте таблицу или скачайте её в CSV.

Можно ли вставить код диаграммы состояний Mermaid или PlantUML?

+

Да: строки переходов вида [*] --> Idle, Idle --> Running : start и Running --> [*] вставляются в конструктор диаграмм состояний как есть. Заголовок stateDiagram-v2, @startuml, заметки и строки direction пропускаются. Составные состояния, записанные как state X { … }, не рисуются; перечислите их внутренние переходы обычными строками.

Диаграмма состояний и блок-схема — это одно и то же?

+

Нет. Блок-схема раскладывает шаги процедуры один за другим; диаграмма состояний показывает состояния, в которых система ждёт, и события, которые переводят её между ними. Турникет — машина состояний, потому что один и тот же толчок действует по-разному, когда он закрыт и когда открыт. В UML аналог блок-схемы — диаграмма деятельности. Пример с турникетом в конструкторе диаграмм состояний показывает разницу.

Как выглядит диаграмма состояний JK-триггера?

+

Два состояния, Q=0 и Q=1, и четыре стрелки: 0X оставляет Q равным 0, 1X устанавливает его в 1, X0 оставляет 1, а X1 сбрасывает в 0. X обозначает безразличный вход, поэтому J = 1, K = 1 (переключение) покрывается переходом 1X из Q=0 и X1 из Q=1. Пример «JK-триггер» в конструкторе диаграмм состояний рисует его вместе с таблицей переходов.

Как нарисовать диаграмму состояний цепи Маркова?

+

В конструкторе диаграмм состояний подпишите каждую стрелку вероятностью перехода, например Солнечно -0.7-> Солнечно, а вероятность остаться на месте нарисуйте петлёй. Когда каждая подпись — вероятность, конструктор диаграмм состояний читает список как цепь Маркова: таблица становится матрицей переходов, а любое состояние, у которого исходящие вероятности в сумме не дают 1, отмечается.

Насколько большой автомат может нарисовать конструктор диаграмм состояний?

+

Конструктор диаграмм состояний рисует до 16 состояний и 48 переходов. Каждая раскладка проверяется перед показом, и если автомат нельзя нарисовать без соприкосновения подписей, конструктор так и говорит, вместо того чтобы рисовать клубок: переключитесь между «слева направо» и «сверху вниз», сократите подписи или разделите автомат на части.

Может ли ИИ-генератор нарисовать иллюстрированную или рукописную диаграмму состояний?

+

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

Нарисуйте свою диаграмму состояний

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

Открыть конструктор диаграмм состояний