Что такое конечные автоматы


Содержание

Автомат Конечный

Математическая модель устройства с конечной памятью, преобразующего дискретную информацию. А. к. является одним из важнейших видов управляющих сиcтем. Содержательно А. к. можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, наз. тактовыми моментами, в одном из псостояний По входному каналу в каждый тактовый момент в устройство поступают сигналы — буквы входного алфавита. В те же моменты по выходному каналу устройство выдает сигналы — буквы выходного алфавита. С соответствующей точки зрения, к таким устройствам могут быть отнесены формальные системы, реальные автоматы, живые организмы и т. п. Существуют различные подходы к определению понятия А. к. При макроподходе, т. е. когда интересуются только внешним поведением устройств, определение А. к. может быть дано в виде совокупности функций, либо в виде конечного ориентированного графа, либо в алгебраич. форме — в виде конечной алгебры с унарными операциями (см. Автоматов способы задания). При микроподходе А. к. задается множеством элементов и схемой их соединения, т. е. в этом случае кроме функционирования описывается и строение автомата, в связи с чем это понятие обычно наз. структурным, а сами А. к.- структурными автоматами, или автоматными сетями. Макроподход. А. к.- это система где — конечные, как правило непустые, алфавиты, наз., соответственно, входным алфавитом, множеством состояний и выходным алфавитом; — функция переходов, отображающая множество в — функция выходов, отображающая в В. Такие А. к. иногда называются автоматами Мили. В случае, когда функция выходов отображает Sв В(т. е. не зависит от букв входного алфавита), А. к. называют а в-томатом Мура. Всякий автомат Мура является автоматом Мили. Важнейшей характеристикой А. к. является его поведение (см. Автомата поведение), к-рое может быть определено по-разному. В зависимости от того, какой тип поведения рассматривается, А. к. подразделяются на преобразователи, акцепторы (распознаватели), генераторы и др. Чтобы определить основные виды поведения А. к., функции j и y распространяют на множество (где — множество всех слов в алфавите А, включая пустое слово ): (здесь а запись обозначает слово, получаемое путем приписывания буквы акслову a). Таким образом распространенные функции для произвольных и описывают соответственно состояние, в к-рое переходит автомат из состояния s под действием входного слова и выходную букву, к-рая выдается автоматом в момент поступления последней буквы входного слова Пусть обозначает начало длины слова — слова в алфавитах определяемые следующим образом: Функции описывают уже последовательность всех состояний, в к-рых находился автомат при поступлении в него букв слова а также выходное слово, т. е. последовательность букв выходного алфавита, выдаваемых автоматом под воздействием входного слова Тернарное отношение наз. функционированием А. к. =( А, S, В,j, y). Функции естественно распространяются и на бесконечные последовательности (сверхслова) в алфавите А. Поэтому под функционированием А. к. иногда понимают отношение вида F, в к-ром a — произвольное сверхслово. В этом случае значение функции определяется как множество всех тех и только тех состояний, к-рые встречаются в последовательности бесконечное число раз. А. к. с выделенным начальным состоянием наз. инициальным и обозначается Поведением инициального А. к. наз. обычно одно из следующих трех отношений. 1) Функция отображающая (или , где — множества всех сверхслов в алфавитах Аи Всоответственно). Эта функция наз. функцией вычислимой, или реализуемой, инициальным А. к. 2) Множество определяемое для выделенного множества заключительных состояний так: Множество наз. событием, представимым А. к. с множеством заключительных состояний. 3) Множество значений функции для всевозможных называемое множеством, перечислимым данным 4) Множество определяемое для системы подмножеств множества следующим образом: Множество наз. сверхсобытием, представимым А. к. с системой’ заключительных подмножеств состояний. А. к. с поведением типа 1) наз. конечным преобразователем, ас поведением типа 2) — конечным распознавателем, или акцептором. Если в качестве входного и выходного алфавитов взять декартовы произведения X соответственно, то поведением типа 1) будет набор из га функций от таргументов. В этом случае говорят, что автомат имеет твходов и n выходов, причем алфавиты наз., соответственно, входными и выходными алфавитами такого автомата. Класс событий, представимых А. к., и класс функций, вычислимых А. к., могут быть описаны различными математич. средствами. Основной результат состоит в том, что события, представимые А. к., совпадают с так наз. регулярными событиями, а функции, вычислимые А. к., совпадают с ограниченно-детерминированными функциями. Кроме того, класс множеств, перечислимых А. к., совпадает с классом событий, представимых А. к. Относительно поведений 2), 3) и 4) автоматы Мура эквивалентны автоматам Мили в том смысле, что для всякого автомата Мили найдется эквивалентный ему, т. е. имеющий то же самое поведение, автомат Мура, и обратно. Для поведения 1) это неверно. Однако, если в автоматах Мура вместо брать функции вида то автоматы Мура будут эквивалентны автоматам Мили. Автомат Мура наз. автономным автоматом, или генератором, если функция переходов не зависит от букв входного алфавита. Под поведением инициального автономного автомата принято понимать сверхслово где . Эта последовательность является периодической с нек-рым предпериодом. А. к. паз. переходной системой, если B-S и для всякого s из Sимеет место или же если выходной алфавит В — пустой. Таким образом, переходная система полностью определяется тройкой Понятия А. к. и функционирования А. к. могут быть определены различными эквивалентными способами (см. Автоматов способы задания, Автомата поведение). Широкое распространение получили так наз. канонические уравнения. Для произвольного слова пусть обозначает t- юбукву слова , а — длину слова Тогда функционирование FА. к. состоит из всех тех и только тех троек слов , к-рые удовлетворяют условиям: 1) 2) для всякого tтакого, что имеют место равенства Для определения поведения инициального А. к. необходимо добавить равенство Совокупность этих равенств однозначно определяет поведение инициального А. к. и наз. обычно каноническими уравнениями. Канонич. уравнения широко используются в задачах анализа и синтеза автоматов. Микроподход. Рассматривается множество элементов, состоящее из определенных выше А. к. с входными и выходными алфавитами вида где А — конечный алфавит, одинаковый для всех элементов. Правила построения структурных А. к. из элементов описывают дозволенные соединения (отождествления) входов и выходов, а также определяют множества входов и выходов, получаемых А. к. Важнейшим примером таких А. к. являются логические сети (л. с.). Ниже приводится один из вариантов этого понятия. В рассматриваемом случае и элементами являются так наз. функциональные элементы (ф. э.), представляющие собой А. к. с одним состоянием, а также специальные автоматы Мура, наз. задержками. Последние характеризуются тем, что они имеют два состояния, к-рые обычно обозначаются буквами О и 1 входного алфавита, при чем функции переходов и выходов удовлетворяют условиям: Поскольку ф. э. имеет только одно состояние, то он полностью характеризуется функцией выходов y, являющейся в этом случае булевой функцией от паргументов, где п — число входов ф. э. Элементы являются исходными л. с., входы и выходы к-рых совпадают, соответственно, с входами и выходами элементов. Дальнейшее построение более сложных л. с. производится по следующим правилам. 1. Объединение двух л. с. есть л. с., входами и выходами к-рой являются, соответственно, входы и выходы объединяемых л. с. (рис. 1). 2. Результат отождествления любых двух входов л. с. является л. с., выходы к-рой совпадают с выходами исходной л. с., а входами служат все входы исходной л. с., кроме одного из отождествленных (рис. 2). 3. Результат отождествления выхода одной л. с. с входом другой л. с. есть л. с. Ее входами являются все входы первой л. с. и те входы второй л. с., к-рые не отождествлялись с выходом первой л. с.; ее выходами являются все выходы обеих л. с. (рис. 3). 4. Результат отождествления выхода л. с., являющегося выходом задержки, с произвольным входом этой же л. с. есть л. с., входы к-рой — все входы исходной л. с., кроме отождествленного, а выходы — все выходы исходной л. с. (рис. 4). (При нек-рых ограничениях это правило может быть применимо и к выходам, не являющимся выходами задержек.) 5. В любой л. с. можно объявить выходами только часть выходов, определенных согласно правилам 1 — 4. Л. с., получаемые из ф. э. с помощью правил 1, 2, 3, 5, наз. обычно схемами из ф. э. Функционирование л. с. содержательно можно описать следующим образом. Пусть в момент tвсем входам л. с. приписаны входные буквы и определены состояния задержек. Тогда в этот же момент всем входам и выходам элементов л. с., в частности всем выходам л. с., будут приписаны буквы в соответствии со следующими правилами. Если входам ф. э. с выходной функцией приписаны, соответственно, буквы то его выходу в этот же момент будет приписана буква, являющаяся значением Если задержка находится в момент tв состоянии a, то в этот же момент ее выходу приписывается буква а. Отождествленным входам и выходам приписываются одинаковые буквы. Далее, в момент состояния задержек определяются входными буквами в момент t, как было определено выше, т. е. Таким образом, при фиксированных начальных состояниях задержек л. с. определяет нек-рое отображение входных последовательностей в алфавите в выходные последовательности в алфавите где — число входов, а n, — число выходов л. с. Класс таких отображений совпадает с классом функций, реализуемых А. к. в первом смысле (т. е. с классом ограниченно детерминированных функций), поскольку описанное выше функционирование л. с. совпадает с функционированием А. к. ( ), где — число входов, — число выходов л. с., S — декартово произведение множеств состояний всех задержек л. с.; функция переходов ф является покоординатным применением функций переходов задержек, а функция выходов определяется в соответствии с вышеописанным функционированием ф. э. и задержек. Пусть, напр., элементами являются задержки (к-рые на рисунке изображаются прямоугольниками) и ф. э. с выходными функциями (треугольники с соответствующими символами функции). На рис. 5 изображена л. с., к-рая в тактовый момент tвыдает выходную букву 1 в том и только в том случае, если среди входных букв в моменты 0, 1, 2, .. ., tсодержится нечетное число букв 1 (задержка в начальный момент имеет состояние 0; буквами а и bобозначены, соответственно, вход и выход л. с.). Если обозначить через s(t), a(t), b(t), соответственно, состояние, входную букву и выходную букву в момент t, то функционирование такой л. с. можно задать следующими канонич. уравнениями: При макроподходе этот автомат можно представить в виде (mod 2) и Понятие А. к. явилось отправным пунктом современной автоматов теории, изучающей также различные модификации и обобщения этого понятия.

Детерминированные конечные автоматы

Определение:
Детерминированный конечный автомат (ДКА) (англ. deterministic finite automaton (DFA)) — набор из пяти элементов [math]\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math] , где [math]\Sigma[/math] — алфавит (англ. alphabet), [math]Q[/math] — множество состояний (англ. finite set of states), [math]s[/math] — начальное (стартовое) состояние (англ. start state), [math]T[/math] — множество допускающих состояний (англ. set of accept states), [math]\delta[/math] — функция переходов (англ. transition function).

Содержание

Процесс допуска [ править ]

Изначально автомат находится в стартовом состоянии [math]s[/math] . Автомат считывает символы по очереди. При считывании очередного символа [math]p_i[/math] автомат переходит в состояние [math]\delta(q, p_i)[/math] , где [math]q[/math] — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

Определение:
Будем говорить, что автомат допускает (англ. accept) слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.

Замечание. Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную «дьявольскую вершину» (также тупиковое состояние, сток), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

Способы представления [ править ]

Диаграмма переходов [ править ]

Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.

[math]\bigcirc[/math] — нетерминальное состояние, [math]\circledcirc[/math] — терминальное состояние, Стрелка [math]\downarrow[/math] указывает на начальное состояние.

Пример Описание
Автомат для поиска образца в тексте для строки [math]abbab[/math] .
Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math] ,без «дьявольской вершины».
Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math] , с «дьявольской вершиной».

Таблица переходов [ править ]

Таблица переходов [math]T (|Q| \times |\Sigma|)[/math] , дающая табличное представление функции [math]\delta[/math] .

[math]M = (Q, \Sigma , \delta, q_0, F)[/math] , где

  • [math]Q = [/math] ,
  • [math]\Sigma = \<0, 1 \>[/math] ,
  • [math]q_0 = S_1[/math] ,
  • [math]F = [/math] ,
  • [math]\delta[/math] — функция переходов, представленная таблицей:
[math]0[/math] [math]1[/math]
[math]S_1[/math] [math]S_2[/math] [math]S_1[/math]
[math]S_2[/math] [math]S_1[/math] [math]S_2[/math]

Автоматные языки [ править ]

Определение:
Мгновенное описание (конфигурация) (англ. snapshot) — пара [math]\langle q, \alpha \rangle[/math] , где [math]q[/math] — текущее состояние, [math]\alpha[/math] — оставшиеся символы.

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за один шаг [math](\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)[/math] , если:

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за конечное число шагов [math](\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)[/math] , если [math]\exists n:[/math]

  • [math]\alpha = c_1 c_2 . c_n\beta[/math] ,
  • [math]\langle q, c_1 c_2 c_3 . c_n\beta \rangle \vdash \langle u_1, c_2 c_3 . c_n\beta \rangle \vdash \langle u_2, c_3 . c_n\beta \rangle \vdash . \vdash \langle u_, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math] .
Лемма:
[math]\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle[/math] .
Доказательство:
[math]\triangleright[/math]
[math]\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.[/math]
[math]\triangleleft[/math]
Определение:
Множество [math]L(\mathcal)=\<\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\>[/math] называется языком автомата (англ. automata’s language) [math]\mathcal[/math] .

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

Определение:
Множество языков всех ДКА образует множество автоматных языков [math]\mathrm[/math] .

Изоморфизм двух автоматов [ править ]

Определение:
Автоматы называются изоморфными (англ. isomorphic), если существует биекция между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные — начальным
Задача:
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу. Гарантируется, что все состояния автоматов достижимы.

Алгоритм [ править ]

Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке обхода в глубину по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть [math]O(N + M) [/math] , где [math] N[/math] — суммарное число вершин в автоматах, [math] M[/math] — суммарное число ребер.

Недетерминированные конечные автоматы

Автор: Сергей Холодилов
The RSDN Group
Источник: RSDN Magazine #2-2007

Опубликовано: 30.07.2007
Исправлено: 10.12.2020
Версия текста: 1.0

Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.

Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела :)

Просто конечные автоматы

Скорее всего, все более-менее знают, что такое конечные автоматы. Проблема в том, что я, например, знаю три варианта: конечные автоматы Мура, конечные автоматы Мили и «просто» конечные автоматы. Поскольку дальше нам потребуется вполне конкретное определение, имеет смысл ввести его здесь.

Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:

  • Q – конечное множество состояний.
  • Σ – конечное множество входных символов.
  • δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.
  • q 0 – начальное состояние, принадлежит Q.
  • F – множество допускающих состояний, является подмножеством Q.

И функционирующие следующим образом:

  • Автомат начинает работу в состоянии q 0 .
  • Если автомат находится в состоянии q i , а на вход поступает символ b, то автомат переходит в состояние δ(q i , b).

ПРИМЕЧАНИЕ

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

Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.

ПРИМЕЧАНИЕ

Это определение конечного автомата используется в теории вычислений. Автоматы Мура и Мили используются, в основном, при проектировании цифровой аппаратуры.

Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой (да, этот здоровенный треугольник в душе – стрелочка), допускающее (в данном случае оно одно) – двойным кружком.

Рисунок 1. Простой детерминированный конечный автомат.

Второй вариант изображения автоматов – таблица переходов.

1
-> q 0 q 1 q 0
* q 1 q 1 q 0
Таблица 1. Тот же самый конечный автомат.

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

Добавляем недетерминированность

Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:

  • δ – функция перехода. Аргументы – состояние и входной символ, результат – множество состояний (возможно – пустое) .
  • Если автомат находится в состоянии q i , а на вход поступает символ b, то автомат переходит во множество состояний δ (q i , b) . Если автомат находится во множестве состояний , то он переходит во множество состояний, получаемое объединением множеств δ(q i , b).

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

На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.

Рисунок 2. Простой недетерминированный конечный автомат.

Этот же автомат в виде таблицы:

1
-> q 0
q 1 Ø
* q 2 Ø Ø
Таблица 2. Тот же самый недетерминированный конечный автомат.

Разберёмся, как он работает.

Подход №1

Допустим, на вход автомату поступила цепочка «100100».


До Вход Описание После
Автомат начинает работу в множестве состояний
1 Из состояния q 0 по символу 1 существует только один переход, в q 0 же.
Из состояния q 0 по символу 0 существует два перехода, в q 0 и в q 1 .
Из состояния q 0 по символу 0 существует два перехода, в q 0 и в q 1 , из состояния q1 – один переход, в q 2 . Поскольку автомат находится в двух состояниях, множества объединяются.
1 Автомат находится в трёх состояниях, но из q 1 и из q 2 не существует переходов по символу 1 (т.е. значение функции перехода из этих состояний по входному символу 1 – пустое множество). В итоге остаётся только q 0 .
И т.д.
И т.п. Так как в получившемся множестве состояний есть q 2 – допускающее состояние, автомат признаёт цепочку корректной.
Таблица 3. Обработка цепочки 100100.

Подход №2

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

Рисунок 3. Обработка цепочки 100100

В данном случае мы несколько удаляемся от определения НКА (множества состояний не представлены так явно). Картинка основана на следующей идее: каждый раз, когда по входному символу возможен переход в несколько состояний, порождается новая ветка вычислений, когда переходов нет – ветка «засыхает». Если хоть одна из «живых» веток ведёт в допускающее состояние – цепочка допущена.

В общем, подходы дают аналогичные результаты, за исключением одной мелочи. Слегка изменённый НКА, изображённый на рисунке 4, допускает любую цепочку символов <0, 1>, содержащую два нуля подряд. Если каждый раз честно порождать новую ветку, то при обработке цепочки «1001001….» получится дерево, изображённое на рисунке 5. Понятно, что две нижние ветки полностью совпадают (они представляют одинаковые состояния автомата, получают одинаковые входы, значит и результаты будут одинаковые), более того, каждый раз, когда в цепочке будет встречаться 00, будет порождаться ещё одна точно такая же ветка.

Рисунок 4. Немного изменённый НКА

Рисунок 5. Обработка цепочки 1001001.

Можно добавить слияние одинаковых веток, но это уменьшит наглядность. В подходе, основанном на множествах, слияние происходит автоматически – множество не может содержать два одинаковых элемента.

Подход №3

Наименее формальный подход к описанию работы НКА основан на том, что он «угадывает». Вернёмся к автомату на рисунке 2 и цепочке «100100».

До Вход Описание После
Автомат начинает работу в состоянии q 0
q 0 1 Из состояния q 0 по символу 1 существует только один переход, в q 0 же. q 0
q 0 Из состояния q 0 по символу 0 существует два перехода, в q 0 и в q 1 . Но! Автомат угадал , что эта последовательность нулей – ещё не конец цепочки. Поэтому остаёмся в q 0. q 0
q 0 И т.д. q 0
q 0 1 И т.п. q 0
q 0 А вот теперь автомат угадал , что это завершение, и что следующим входным символом тоже будет 0 (иначе нет смысла переходить в q 1 – из него нет переходов по 1). Переход в q 1 q 1
q 1 Из q 1 только один переход – в q 2 . Цепочка допущена. q 2
Таблица 4. Обработка цепочки 100100.

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

… и эпсилон-переходы

Небольшое полезное расширение стандартного НКА – ε-НКА, или НКА с эпсилон-переходами.

«Эпсилон-переходом» называется переход между состояниями, который может быть выполнен автоматом «просто так», без входного символа. На графах и в таблицах такие переходы обычно помечаются символом ε.

ПРИМЕЧАНИЕ

В замечательной программе JFLAP, скриншоты из которой используются в качестве рисунков, ε-переходы почему-то обозначаются символом λ, но я нашёл в себе силы поправить картинки.

На рисунке 6 изображён пример ε-НКА.

Рисунок 6. НКА с ε-переходами.

Как это ни удивительно, но на этом немного странном примере продемонстрировано одно из наиболее полезных свойств ε-переходов – возможность простого объединения нескольких автоматов в один. В данном случае объединяемыми автоматами являются НКА, изображённые на рисунке 7, а результирующий автомат допускает цепочки, допустимые хотя бы одним из них.

Рисунок 7. Составные части автомата, показанного на рисунке 6.

Кроме того, обратите внимание, что никаких дополнительных ограничений на ε-переходы не накладывается. То есть:

  • из одного состояния ε-НКА может выходить сколько угодно как обычных, так и ε-переходов;
  • может существовать цепочка из нескольких последовательных ε-переходов;
  • автомат может проходить цепочку целиком, частично или не проходить ее вообще (если у ε-НКА есть другие варианты поведения).

В общем, граф/таблица переходов автомата выглядят так, как будто во входном алфавите появился ещё один символ – ε, а его работа так, будто в любом месте обрабатываемой цепочки (в начале, в конце, между символами) находится произвольное количество этих символов. При этом для каждого состояния есть как минимум один переход по ε – в себя.

… и более формально

Введём понятие ε-замыкание .

  • ε-замыканием состояния q i называется множество состояний ε-НКА, в которые из q i можно попасть по цепочке ε-переходов. Как минимум, в это множество входит само q i .
  • Функцию, аргументом которой является состояние, а значением – соответствующее ε-замыкание, назовём eclose .

Функцию eclose можно определить так:

А теперь мы можем строго определить функционирование ε-НКА.

  • Автомат начинает работать во множестве состояний eclose(q 0 ).
  • Если автомат находится во множестве состояний , то он переходит во множество состояний, получаемое ε-замыканием всех состояний из объединения множеств δ(q i , a).

И почему это круто

Допустим, вам нужен автомат, распознающий двоичные, десятичные и шестнадцатеричные числа в стандартном ассемблерном формате (я понимаю, что такие ситуации происходят в вашей жизни нечасто, но я и так сломал голову в поисках не слишком искусственного примера). То есть, допустимая строчка должна описываться одним из следующих утверждений:

  • Состоит из одной или более цифр (0-9), может завершаться символом «d» (например, «1234»).
  • Состоит из одного или более символов «0», «1», завершается символом «b» (например, «0100b»).
  • Начинается с десятичной цифры, потом идёт любое количество символов 0-9 и a-f, завершается символом «h» (например, «0ab4h»).

Решение показано на рисунке 8.

Рисунок 8. ε-НКА, распознающий числа в ассемблерном формате

Что в первую очередь радует в этом конечном автомате – то, что он понятен и изменяем . Посмотрев на граф, можно практически сразу сказать, что делает автомат, и убедиться, что он соответствует ТЗ. А если задание поменяется, граф будет достаточно просто изменить. Например, если добавляется ещё одна система счисления, нужно просто нарисовать соответствующий автоматик и присоединить его к начальному и допускающему состояниям исходного автомата ε-переходами.

Выполняющий аналогичную задачу ДКА приведён на рисунке 9 (что за цифры под состояниями – разберёмся позже, пока не обращайте внимания), он тоже не слишком сложен, более того, в данном случае даже получилось меньше состояний (а вот переходов больше, 78 против 60). Но сравните: насколько ДКА более запутан! Попробуйте, глядя на него, понять, что делает этот автомат, проверить, правильно ли он это делает, попробуйте добавить или убрать систему счисления, ещё как-нибудь изменить ТЗ…

Рисунок 9. ДКА, распознающий числа в ассемблерном формате.

ПРИМЕЧАНИЕ

Помимо прочего, это ещё и не совсем правильный ДКА. В «воистину правильном» ДКА из каждого состояния есть переход по каждому символу входного алфавита, определением для ДКА не предусмотрено ситуации пустого множества состояний и «засыхания ветки вычислений».

Поэтому для полного соответствия нужно добавить в автомат ещё одно состояние, в которое должны сходиться все переходы по «непредусмотренным» символам, а выхода из этого состояния не будет – по любому символу следует переход в себя. Иногда такие состояния называют «дьявольскими».

В общем, мораль такая: с точки зрения проектирования конечных автоматов, ε-НКА – язык более высокого уровня, чем ДКА. Вычислительные возможности ε-НКА, просто НКА и ДКА совпадают – для любого ε-НКА теоретически можно построить ДКА, описывающий тот же язык (этим мы скоро займёмся), но проектировать ε-НКА гораздо, гораздо проще и удобнее.

Реализация методом «в лоб»

На детерминированном компьютере проще всего реализовывать НКА, основываясь на его определении. То есть, хранить множество текущих состояний, а при обработке очередного входного символа, переходить из каждого состояния в соответствующее множество и объединять результаты.

  • Таблица, с оригинальным именем table, по ключу, состоящему из состояния и символа, возвращает множество состояний.
  • Множества объединяются оператором «+=».
  • Множество current содержит текущие состояния.
  • input – обрабатываемый в данный момент входной символ.

Обработка входного символа:

Производительность

На первый взгляд, количество операций, необходимое для обработки одного символа можно оценить как O(M), где M – количество состояний автомата. Но эта оценка верна, только если вам удастся реализовать объединение множеств за константное время, не зависящее ни от размера первого множества, ни от размера второго.

Типичная сложность реализации объединения множеств линейно зависит от размера второго множества. Поскольку оценить мы его можем только как O(M), в результате сложность обработки одного символа – O(M 2 ), обработка строки длиной N – O(N*M 2 ).

Можно переписать код, например, так:

Но и в этом случае O(M 2 ) никуда не уходит, просто прячется внутри метода normalize.

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

ε-переходы

При желании таким же несложным способом можно реализовать и ε-НКА – нужно перед началом обработки данных и после обработки каждого символа подавать на вход автомату ε, пока множество состояний не перестанет изменяться. Примерно так:

Это ужасающе неэффективно, но зато работает.

Немного подумав, можно вспомнить про формальное определение ε-НКА через ε-замыкания, и сообразить, что множество eclose(q i ) – фиксировано, и его нужно вычислить только один раз, причём до начала работы автомата.

В результате, получаем вот такой код:

Этот кусок тоже имеет сложность O(M 2 ).

Реализация преобразованием в ДКА


Теория



Рассмотрим произвольный НКА с тремя состояниями – q 0 , q 1 , q 2 .

Независимо от своей внутренней структуры, в каждый конкретный момент этот НКА может находиться в одном из следующих множеств состояний:

И всё, других вариантов нет. Причём переход между множествами состояний чётко детерминирован – это просто объединение значений функции перехода для каждого из состояний, и сами значения и их объединения тоже находятся в этом списке.

Обобщая наблюдения до произвольного НКА с любым количеством состояний, мы можем определить следующий ДКА:

  • его состояниями будут множества состояний НКА (цифры под состояниями ДКА на рисунке 9 обозначали соответствующие ему состояния НКА).

  • входной алфавит – такой же, как у НКА
  • функция перехода будет «правильным образом» сопоставлять множеству и входному символу другое множество.

  • начальным состоянием будет множество, состоящее только из начального состояние НКА.

  • допускающими будут те состояния ДКА, которые содержат хотя бы одно допускающее состояние НКА.

Идея преобразования основана на том, что множество подмножеств конечного множества состояний – конечно, то есть, как бы НКА не крутился, он всегда находится в одном из конечного множества состояний.

ПРИМЕЧАНИЕ

Если мысль о том, что множества состояний одного автомата являются состояниями другого автомата, пока что плохо влезает в вашу голову, можно представить то же самое менее абстрактно. Для НКА с тремя состояниями, обозначим состояния ДКА следующими строчками:

Назначим среди этих состояний правильное начальное (оно должно соответствовать начальному состоянию НКА) и допускающие, нарисуем таблицу для функции переходов, получим ДКА.

Для НКА с большим количеством состояний – по аналогии.

С использованием индукции достаточно просто доказывается, что сконструированный ДКА описывает тот же язык (допускает точно те же цепочки символов), что и исходный НКА. Эта задача оставляется читателю в качестве упражнения :)

СОВЕТ

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

Добавляем ε-переходы

Конструирование ДКА, соответствующего заданному ε-НКА, немного отличается – нужно в нескольких местах заменить слова «состояние q i » на «ε-замыкание состояния q i ». Вот эти места:

  • функция перехода ДКА будет «правильным образом» сопоставлять множеству и входному символу другое множество.

  • начальным состоянием ДКА будет ε-замыкание начального состояние ε-НКА.

Доказательство идентичности описываемых автоматами языков аналогично доказательству для обычного НКА.

ПРИМЕЧАНИЕ

Таким образом, можно считать доказанным, что любой язык, описываемый ε-НКА, может быть описан обычным ДКА. А поскольку обратное очевидно (ДКА это просто частный случай ε-НКА), вычислительная мощность ДКА и ε-НКА совпадают.

Просто хотелось отдельно отметить этот важный теоретический результат :)

Алгоритм


Состояния ДКА

Для начала оценим количество состояний «теоретического» ДКА. Если НКА имеет M состояний, то состояниями ДКА будут все подмножества множества . Поскольку каждое из q i может входить или не входить в подмножество, мы получаем 2 M состояний ДКА.

Такое количество состояний немного пугает, но, к счастью, часто подавляющее большинство состояний оказывается недостижимым (то есть, не существует последовательности переходов, которая приводит автомат в такое состояние из начального), поэтому их можно просто отбросить, и это никак не повлияет на описываемый ДКА язык.

Но часто – не значит всегда. Пример НКА, ДКА которого будет содержать 2 M-1 состояний, приведён на рисунке 10. Вставляя «в хвост» НКА дополнительные состояния, можно неограниченно увеличивать количество состояний ДКА.

Рисунок 10. Неудачный НКА.

Генерация ДКА

Возможны два подхода:

  • Сначала сгенерировать все состояния ДКА, которые только могут потребоваться, установить между ними связи, а потом избавляться от недостижимых состояний.
  • Сразу же генерировать только достижимые состояния.

Мы пойдём вторым путём. Основная идея алгоритма:

  • Начинаем с начального состояние ДКА – eclose(q 0 ). Оно достижимо по определению.
  • Если состояние достижимо, то все состояния, в которые из него можно попасть, тоже достижимы.
  • Из состояния q i можно попасть в те состояния, которые являются значением δ(q i , x), где δ – функция перехода ДКА, а x принадлежит множеству входных символов. Перебрав все входные символы, получим все такие состояния.
  • После чего применяем к полученным состояниям тот же принцип. Остановка – когда все сгенерированные состояния рассмотрены подобным образом.

Производительность

Оценка алгоритма генерации ДКА неутешительна. Количество операций линейно зависит от количества состояний ДКА, а верхняя оценка для них – 2 M . В среднем будет получше, но тоже ничего хорошего – генерация новых состояний, то есть внутренняя часть цикла, это O(M 2 *S) операций (где S – количество символов).

Но зато, после того как ДКА сгенерирован, он обрабатывает любой символ за константное время, а строчку длиной N – за O(N).

Заключение

Возможно (я на это надеюсь!), вам кажется, что всё описано недостаточно строго, или же что описано ужасающе мало. Этих и многих других недостатков лишена замечательная книжка «Введение в теорию автоматов, языков и вычислений», авторы Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман (издательство Вильямс, 2002). Очень рекомендую, правда, вряд ли вы её найдёте в магазинах, разве что на русском выпустят третье издание.

Значительно проще найти книгу «Классика программирования: алгоритмы, языки, автоматы, компиляторы», Мозговой М.В., Наука и Техника, 2006. Тоже хорошая книжка, она менее фундаментальна и строга, ближе к программированию, и содержит куски кода на C#.

Ну а играть с автоматами проще всего в программе JFLAP, которая уже упоминалась выше.

Определение конечных автоматов

Элементы теории автоматов

План:

1. Понятие автомата, принцип работы автомата

2. Способы задания конечных автоматов

3. Общие задачи теории автоматов

Теоретические сведения

Человек всегда стремился к тому, что бы облегчить свой труд, заставляя работать на себя некоторые механические устройства без собственного вмешательства. Вначале это были сказки, затем они стали превращаться в обыденные вещи. Автомобиль, телевизор, стиральные машины, целые производства работают без участия человека. Причем, вмешательство человека в большинстве случаев не требуется, а в ряде случаев, такое вмешательство может привести к негативным явлениям. Понятие «автомат», как некоторое устройство, выполняющее определенный вид действий давно трактуется людьми именно так.

Понятие автомата, принцип работы автомата

Понятие автомат[1] рассматривается в двух аспектах:

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

2. Автомат – математическое понятие, обозначающее математическую модель реальных технических устройств. Автомат это абстрактное устройство, непонятно почему и как оно работает и, вообще, почему оно может работать. В этом аспекте автомат есть «черный ящик», который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно неважно что, как и почему производит те или иные действия.

Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний.

Алгебраическая теория автоматов является разделом теоретической кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.

Общая теория автоматов содержит различные подразделы. В зависимости от предмета изучения она делится на абстрактную теорию автоматов и структурную теорию автоматов.

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


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

Определение конечных автоматов

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

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

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

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

Считается, что первым программным устройством, созданным человеком, были часы. Часовые механизмы с помощью пружины, приводящей в действие шестеренки и кулачковые механизмы, зубчатые колеса и рычаги, осуществляют ряд определенных действий. Примером такого часового механизма могут быть знаменитые часы на Центральном театре кукол в Москве, где он приводит в действие двенадцать сказочных героев, расположенных на циферблате[2].

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

1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал «железного» слугу — автомат, который выполнял в доме обязанности привратника.

2. Астроном Иоганн Мюллер (Региамонтан) (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана II.

3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. Он создал образ механической утки, точной копии своего живого двойника — плавала, чистила перья, глотала с ладони зерна. Его механический флейтист, исполнявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.

4. Русский изобретатель 19 в. А. М. Гамулецкий создал целый механический кабинет, в котором было множество сконструированных им автоматов. Здесь в том числе была и говорящая голова чародея и амур, играющий на арфе, которые поражали воображение современников.

5. Первый примитивный арифмометр сконструировал в 1641 г. Блез Паскаль. Толчком для открытия были мучения его отца – налогового, инспектора, который днями и ночами работал с большими вычислениями. Изобретя арифмометр, восемнадцати летний сын избавил отца от сложных вычислений, а миру подарил первый калькулятор, производящий сложение и вычитание чисел.

6. Первый шахматный автомат был построен в 1890 г. испанским инженером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).

7. Первую вычислительную машину с автоматическим управлением создал Чарльз Баббедж в 1822 г. Он спроектировал арифмометр, который имел запоминающие и арифметические устройства. Эти устройства стали прототипами аналогичных устройств современным ЭВМ.

Виды автоматов.

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

Любой автомат имеет собственные базовые множества, которые включают в себя:алфавит входа, алфавит выхода, множество состояний автомата.

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

В работе конечных цифровых автоматов важным понятием является время.

Автоматы можно классифицировать по различным признакам.

1. По виду деятельности автоматы делятся на: информационные, управляющие и вычислительные.

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

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

К вычислительным автоматам относятся микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.

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

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

3. Цифровые автоматы— автоматы, которые преобразует цифровую информацию. В таком автомате входные сигналы задаются в виде конечного множества мгновенных символов: их длительность настолько мала, что ею можно пренебречь. За фиксированное время происходит преобразование входных символов, а на выходе происходит скачкообразный переход из одного состояния в другое состояние.

4. Абстрактные автоматы —отображающие множество слов входного алфавита Х во множество слов выходного алфавита Y.

Абстрактный автомат есть:

Алгоритм действия некоторого преобразования кодовых последовательностей,

Закон преобразования входного алфавита в выходной.

5. Синхронные и асинхронные автоматы. В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, автоматы делятся насинхронные и асинхронные автоматы.

В синхронных автоматах продолжительность входных сигналов и время переходов согласовано между собой. Они используются в вычислительных комплексах, АСУ и т.д.

В асинхронных автоматах продолжительность входных сигналов и время переходов не согласовано между собой. Они зависят от внешних источников — различных событий, а интервал дискретности является переменным (например, в кодовых замках). В асинхронных автоматах очередное изменение значений входных сигналов может произойти только при условии, что закончился переходный процесс, вызванный предыдущим изменением этих сигналов.

6. Автоматы делятся на конечные и бесконечные автоматы. Если в основании классификации лежит объем памяти, то различие заключается в том, имеет ли автомат конечное или бесконечное число внутренних состояний.

Под бесконечнымавтоматом обычно понимают определенную математическую идеализацию представлений об автомате, имеющую бесконечное число состояний. Память такого автомата потенциально может неограниченно возрастать. Например, известные абстрактные автоматы Поста и Тьюринга являются бесконечными автоматами, но сама ЭВМ или ее отдельные части — конечными автоматами.

7. Автоматы делятся на детерминированные и вероятностные автоматы. Если в основании классификации лежит механизм случайного выбора, то различают детерминированные и вероятностные (стохастические) автоматы.

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

В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.

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

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

Математическая модель цифрового автомата с одним входом задается пятью объектами:

X- конечное множество входных символов, входной алфавит:

Y- конечное множество выходных символов, выходной алфавит:

конечное множество состояний автомата:

δ(q, х) — функция перехода автомата из одного состояния в другое: (Q х X) ®Q;

функция выхода автомата: (Q x Х) ® Y.

Таким образом, конечный автомат С= (X, Q, У, δ, λ.) определяется рекуррентными соотношениями

q(0) = q, q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),

t- дискретизированный момент времен или это есть образ монотонной функции t:. Т ® N, причем Т — обычное непрерывное время, N — множество натуральных чисел.

Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г) – показывает число изменений, произошедших до момента времени Г.

Примером дискретизации служит обычный кинематограф: время разбито на интервалы длительностью 1/24с. Человеческий глаз воспринимает следование дискретных кадров как непрерывное движение.

9. Синхронные автоматы делятся на автоматы Мили и автоматы Мура. В зависимости от способа организации функции выхода синхронные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).

В автоматах Мили— выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент времени (t-1). Математической моделью таких автоматов служит система уравнений:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t-1), х(t)),

В автоматах Муравыходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени t. Математической моделью таких автоматов является система:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t)),

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

10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущими входными символами, т.е. в этом автомате все состояния эквивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неизменна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.

11 Логическиеавтоматы – есть автоматы у которых входной алфавит состоит из 2 т двоичных наборов длины т, а выходной — из 2 n двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.

Конечные состояния машины — Finite-state machine

Конечный автомат ( КА ) или конечно-автомат ( FSA , множественное число: автоматы ), конечный автомат , или просто состояние машины , представляет собой математическую модель вычислений . Это абстрактная машина , которая может быть в точности один из конечного числа состояний в любой момент времени. FSM может меняться от одного состояния в другое в ответ на некоторые внешние входы ; переход от одного состояния в другое, называется переход . ФСМ определяется списком своих состояний, исходного состояния, а также условия для каждого перехода. Конечные автоматы двух типов — детерминированные конечные автоматы и недетерминированные конечные автоматы . Детерминированный конечный автомат может быть построен эквивалентен любым недетерминированными один.

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

Конечный автомат имеет меньшую вычислительную мощность , чем некоторые другие модели вычислений , такие как машина Тьюринга . Вычислительное различие мощности означает , что есть вычислительные задачи , что машина Тьюринга может сделать , но FSM не может. Это объясняется тем , что FSM в память ограничена числом состояний он имеет. Конечные автоматы изучаются в более общей области теории автоматов .

содержание


Пример: монетный турникет

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

Рассмотренный в качестве государственной машины, турникет имеет два возможных состояния: Locked и разблокирована . Есть два возможных входов , которые влияют на его состояние: положить монетку в слот ( монеты ) и толкающие руки ( толчок ). В заблокированном состоянии, выдвигая на руке не имеет никакого эффекта; независимо от того , сколько раз входной толчок дан, он остается в запертом состоянии. Положив монету — то есть, давая машину на монетный вход — смещает состояние от Locked до разблокирована . В разблокированном состоянии, поставив дополнительные монеты не имеет никакого эффекта; то есть, что дает дополнительные монеты входы не изменяет состояние. Тем не менее, клиент проталкивая руки, давая толчок вход, смещает состояние обратно Locked .

Турникета конечный автомат может быть представлен в виде таблицы перехода состояния , показывающий для каждого возможного состояния, переходы между ними ( на основе входных данных к машине) и выходов в результате каждого входа:

Текущее состояние вход Далее государство Выход
запертый монета разблокирована Разблокирует турникет, так что клиент может протолкнуть.
От себя запертый Никто
разблокирована монета разблокирована Никто
От себя запертый Когда клиент протолкнул, блокирует турникет.

Турникета конечный автомат также может быть представлена в виде ориентированного графа называется диаграмма состояний (выше) . Каждое состояние представлено узлом ( окружность ). Ребра ( стрелка ) показывают переходы из одного состояния в другое. Каждая стрелка маркирована с входом , который вызывает этот переход. Вход , который не вызывает изменение состояния (например, монета вход в разблокирована состоянии) представлен круговой стрелкой возвращения в исходное состояние. Стрелка в Locked узел из черной точки указывает на то, что это начальное состояние.

Основные понятия и терминология

Состояние является описанием состояния системы , которая ждет , чтобы выполнить переход . Переход представляет собой набор действий , которые будут выполняться , когда условие выполняется , или когда событие принимается. Например, при использовании звуковой системы , чтобы слушать радио (система находится в состоянии «радио»), получив «Next» результаты стимула при переходе к следующей станции. Когда система находится в состоянии «CD», «следующий» результаты стимула при переходе к следующему треку. Одинаковые раздражители вызывают различные действия в зависимости от текущего состояния.

В некоторых конечно-машинных представлениях, можно также связать действия с государством:

  • действие записи: выполняется при входе в состоянии, и
  • действие выхода: выполняется при выходе из состояния.

ГЛАВА 5

Наш друг конечный автомат

Использование: часто в качестве определения

Этимология: средневек. англ. stat, от устар. фр. и лат.; устар. фр. estat, от лат. status, между stare и stand — ближе к STAND

Дата: 13 столетие

: режим или условие нахождения b (1): настроение ума или темперамент (2) пребывание в необычном напряжении или волнении

: период или стадия физического существования чего-либо

сущ. (мн. ma-chines)

Использование: часто в качестве определения

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

((Encarta 2004, Quotations))

Введение

Конечный автомат (state machine) (который называют еще и машиной состояний) — весьма полезная концепция, которую удобно использовать для структурирования приложений. Продуманное использование конечных автоматов облегчает организацию и сопровождение как логики пользовательского интерфейса, так и логики приложения. Благодаря этому ваш код будет более гибким и надежным, причем это относится к разработке не только мобильных, но и вообще любых приложений. Поскольку мобильные приложения должны использовать пространство экрана и системные ресурсы эффективно и экономно, конечные автоматы оказываются особенно полезными при разработке мобильного программного обеспечения. Конечные автоматы могут быть использованы для управления тем, какие наборы ресурсов следует удерживать памяти в любой момент времени, а также тем, какие элементы пользовательского интерфейса должны находиться на тех или иных участках экрана мобильного устройства. Конечные автоматы идеально подходят для решения такого рода задач.

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

Что такое конечный автомат?

Каждый, кто прослушал курс цифровых логических схем, должен быть хорошо знаком с понятием «конечный автомат». В этой книге используется упрощенный вариант определения конечного автомата. Если прежде с конечными автоматами вам сталкиваться не приходилось, то знайте, что ничего особо сложного в этом нет, и вполне вероятно, что принцип работы конечного автомата сразу же покажется вам интуитивно понятным.

«Состояние» вашего приложения может быть определено как совокупность значений всех его переменных. Значения всех переменных приложения представляют уникальное состояние, которое изменится лишь в результате воздействия какого-либо внешнего события. Примерами подобного рода событий, способных изменить состояние приложения, являются такие события, как нажатие кнопки пользователем, событие, запускаемое при получении сообщения, или же событие таймера. В любой момент времени ваше приложение находится в каком-то определенном состоянии. В результате возмущения этого состояния приложение переходит в другое состояние. Для определения следующего состояния вашего приложения используется его текущее состояние плюс новые входные данные.

Конечный автомат является средством формальной структуризации этой реальности. Вместо того чтобы использовать все переменные приложения в качестве расширенного определения его состояния, конечный автомат создает единственную переменную, в которой хранится информация о некоем важном аспекте состояния приложения. Такой переменной обычно является элемент перечисления (например, int m_myApplicationState) некоторого множества действительных состояний, определяемого глобально или на уровне класса. Мощь подхода, использующего конечный автомат, обусловлена тем, что он позволяет в явном виде определить действительные состояния для некоторого аспекта вашего приложения и задать соответствующие варианты поведения при переходах приложения из одного состояния в другое.

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

На рис. 5.1 в схематическом виде представлен конечный автомат обучающей игры, позволяющей изучать иностранные слова путем выбора одного из предлагаемых вариантов ответа. Поведение приложения разбито на пять логических состояний. Эти логические состояния существуют независимо от того, будут ли они выбраны нами для введения их определений в конечный автомат. Конечный автомат — это просто формальное описание того, как работает приложение. Она позволяет нам ясно представлять себе различные состояния, в которых может находиться приложение в процессе взаимодействия с ним пользователя.

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

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

Таблица 5.1. Варианты изменения состояний для словарной игры с множественным выбором

Состояние Внешний ввод Следующее состояние
StartScreen Пользователь выбрал вариант «Next Question» AskQuestion
StartScreen Пользователь выбрал вариант «Correct Answer» Запрещенный переход!
StartScreen Пользователь выбрал вариант «Incorrect Answer» Запрещенный переход!
StartScreen Пользователь выбрал вариант «End Game» Запрещенный переход!
AskQuestion Пользователь выбрал вариант «Next Question» Запрещенный переход!
AskQuestion Пользователь выбрал вариант «Correct Answer» CongratulateUser
AskQuestion Пользователь выбрал вариант «Incorrect Answer» ScoldUser
AskQuestion Пользователь выбрал вариант «End Game» Запрещенный переход!
CongratulateUser Пользователь выбрал вариант «Next Question» AskQuestion
CongratulateUser Пользователь выбрал вариант «Correct Answer» Запрещенный переход!
CongratulateUser Пользователь выбрал вариант «Incorrect Answer» Запрещенный переход!
CongratulateUser Пользователь выбрал вариант «End Game» StartScreen
ScoldUser Пользователь выбрал вариант «Next Question» AskQuestion
ScoldUser Пользователь выбрал вариант «Correct Answer» Запрещенный переход!
ScoldUser Пользователь выбрал вариант «Incorrect Answer» Запрещенный переход!
ScoldUser Пользователь выбрал вариант «End Game» StartScreen

Я решил привести в таблице все возможные перестановки переменных, указанных в столбцах «Состояние» и «Внешний ввод», чтобы проиллюстрировать тот факт, что не любое изменение состояния разрешено. Переходы между состояниями, указанными в строках, для которых в столбце «Следующее состояние» содержится пояснение «Запрещенный переход!», недопустимы в нашем приложении. Если приложение пытается каким-либо образом осуществить такое изменение состояния, значит, в логике его выполнения присутствуют ошибки. В случае если предпринимается попытка выполнения недействительного перехода, логика конечного автомата должна возбуждать исключение или, по крайней мере, использовать оператор ASSERT в режиме отладки. Явная идентификация запрещенных переходов между состояниями облегчает отладку приложений.

В листинге 5.1 представлен код, реализующий определенный выше конечный автомат. Этот код соответствует диаграмме переходов, представленной в табл. 5.1 и на рис. 5.1. Обратите внимание на то, что в приведенной ниже функции участки кода, соответствующие различным изменениям состояний, содержат вызовы функций, отключенные с помощью символов комментариев. Эти функциональные вызовы представляют ту часть работы, которая должна быть выполнена для соответствующего изменения состояния, и отключены символами комментариев с той целью, чтобы приведенный ниже код можно было компилировать как независимый блок; реализация вызываемых функций остается за вами. Для определения текущего варианта изменения состояния удобно использовать блок операторов switch/case.

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

Листинг 5.1. Простой код конечного автомата для игры с множественным выбором

StartScreen, AskQuestion, CongratulateUser, ScoldUser

private GameState m_CurrentGameState;

//Конечный автомат, воздействующий на пользовательский интерфейс

//и управляющий переходами приложения в другие состояния в соответствии

//c текущим режимом работы пользователя

private void StateChangeForGame(GameState newGameUIState) <

//Определить, в какое состояние переходит приложение

//Если переход в данное состояние осуществляется из состояния,

//для которого это запрещено, возбудить исключение

if ((m_CurrentGameState != GameState.CongratulateUser) && (m_CurrentGameState != GameState.ScoldUser)) <

throw new System.Exception(«Запрещённый переход!»);

//ЧТО СДЕЛАТЬ: Поместите сюда код, выполняющий следующие операции:

// 1. Скрытие (Hide), отображение (Show) и перемещение (Move)

// элементов управления пользовательского интерфейса

// 2. Настройка переменных/состояния игры, соответствующих

//Если переход в данное состояние осуществляется из состояния,

//для которого это запрещено, возбудить исключение

if ((m_CurrentGameState != GameState.StartScreen)

throw new System.Exception(«Запрещённый переход!»);

//ЧТО СДЕЛАТЬ: Поместите сюда код, выполняющий следующие операции:

// 1. Скрытие (Hide), отображение (Show) и перемещение (Move)

// элементов управления пользовательского интерфейса

// 2. Настройка переменных/состояния игры, соответствующих

//Если переход в данное состояние осуществляется из состояния,

//для которого это запрещено, возбудить исключение

if (m_CurrentGameState != GameState.AskQuestion) <

throw new System.Exception(«Запрещённый переход!»);


//ЧТО СДЕЛАТЬ: Поместите сюда код, выполняющий следующие операции:

// 1. Скрытие (Hide), отображение (Show) и перемещение (Move)

// элементов управления пользовательского интерфейса

// 2. Настройка переменных/состояния игры, соответствующих

//Если переход в данное состояние осуществляется из состояния,

//для которого это запрещено, возбудить исключение

if (m_CurrentGameState != GameState.AskQuestion) <

throw new System.Exception(«Запрещённый переход!»);

//ЧТО СДЕЛАТЬ: Поместите сюда код, выполняющий следующие операции:

// 1. Скрытие (Hide), отображение (Show) и перемещение (Move)

// элементов управления пользовательского интерфейса

// 2. Настройка переменных/состояния игры, соответствующих

throw new System.Exception(«Неизвестное состояние!»);

//Сохранить запрошенное новое состояние в качестве текущего

Явно и неявно определенные конечные автоматы

Планируете ли вы это или не планируете, но ваш код будет так или иначе управляться состояниями. Например, если какой-либо элемент управления необходимо сделать недоступным для пользователя, то разработчики часто добиваются этого, устанавливая для свойств Enabled и Visible этих элементов управления значение false (например, TextBox1.Visible = false;). Для написания кода такого типа существует два возможных подхода, которые рассматриваются ниже

Подход 1: зависящее от специфики конкретной ситуации, децентрализованное, неявное управление состояниями (неудачный подход)

Специализированный стиль проектирования, ориентированный на максимально возможный учет специфики конкретной задачи, часто встречается в тех случаях, когда приложение в процессе разработки постепенно усложняется. Различные аспекты состояния приложения изменяются в разных местах приложения. Данные о состоянии хранятся в таких свойствах элементов управления, как Visible, Enabled, Size или Position. Переменные, используемые для хранения ключевой информации о состоянии, изменяются непосредственно в тех строках кода, где это оказывается необходимым, а загрузка данных и освобождение памяти от них распределяются по всему приложению в зависимости от конкретной ситуации. Развитие событий напоминает «перетягивание каната» между различными частями приложения, поскольку каждая из функций делает все необходимое для выполнения возложенных на нее задач, не обращая никакого внимания на остальную часть приложения. Простейшим примером подобного поведения может служить код, реагирующий на такие события пользовательского интерфейса, как щелчок на кнопке, которой соответствует встроенный код, изменяющий состояние приложения. В листинге 5.2 приведен типичный код, встречающийся в классах формы приложения, соответствующих описанному подходу. Как код события загрузки формы form1, так и код события щелчка кнопки button1 вносят изменения, которые влияют на общее состояние формы.

Листинг 5.2. Неявное изменение состояний приложения (неудачный подход)

//Код, выполняющийся при загрузке формы

private void Form1_Load(object sender, System.EventArgs e) <

//Пользователь щелкнул на кнопке, желая перейти к выполнению

//следующего шага, предусмотренного в данном приложении. Скрыть

//текстовое окно и отобразить окно списка в отведенном для этого месте

private void button1_Click(object sender, System.EventArgs e) <

Подход 2: плановое, централизованное, явное управление состояниями (удачный подход)

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

Листинг 5.3. Явное изменение состояний приложения (удачный подход)

//Определить состояния, в которых может находиться приложение

//Главная функция, которая вызывается

//всякий раз, когда возникает необходимость

//в изменении состояния приложения

void ChangeApplicationState(MyStates newState) <

//Пользователь щелкнул на кнопке, желая перейти к выполнению

//следующего шага, предусмотренного в данном приложении. Скрыть

//текстовое окно и отобразить окно списка в отведенном для этого месте

private void button1_Click(object sender, System.EventArgs e) <

//Вызвать главную функцию, осуществляющую изменение состояния

//Код, выполняющийся при загрузке формы

private void Form1_Load(object sender, System.EventArgs e) <

//Вызвать главную функцию, осуществляющую изменение состояния

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

Постойте-ка! Но ведь речь идет о мобильных приложениях. Разве размер их кода не должен быть меньше размера кода настольных приложений?

Краткий ответ на этот вопрос звучит так: «Нет, не должен». Ваш код вовсе не должен быть меньше по размеру, чем аналогичный код для настольных компьютеров — он должен быть лучше! Среди разработчиков мобильных приложений бытует ошибочная точка зрения, согласно которой при написании кода лучше не разбивать его на отдельные функции, а стараться поместить в любую заданную функцию как можно больше кода и как можно чаще использовать встроенный код. Такой подход противоречит устоявшимся принципам проектирования. Назовем эту тенденцию «оптимизацией под микроскопом».

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

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

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

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

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

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

Сколько конечных автоматов должно быть в приложении?

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

Иногда удобно использовать несколько конечных автоматов в одном приложении. Конечный автомат, который управляет кэшированными данными, извлеченными из базы данных, может использоваться наряду с независимым конечным автоматом, управляющим такими графическими объектами, как перья и кисти, кэшируемыми для их использования в обычных задачах рисования. Третий конечный автомат может управлять выполнением задач фоновыми потоками. И хотя все перечисленные конечные автоматы можно было бы объединить в один «главный конечный автомат», такой комбинированный конечный автомат представлял бы просто формальное объединение всех возможных случаев изменения состояния приложения и не дал бы ничего нового, поскольку состояния, которыми управляют отдельные конечные автоматы, слабо или вообще не коррелируют друг с другом. Точно так же, возможна крайность другого рода, когда вместо создания одного конечного автомата, выполняющего всю работу, предпочитают иметь десятки небольших конечных автоматов, каждый из которых управляет отдельной переменной приложения. Роль ключа к нахождению правильного решения играет корреляция. Если можно выделить набор переменных, объектов или ресурсов, которые тем или иным образом коррелируют между собой, то управление этим набором удобно и целесообразно осуществлять при помощи одного конечного автомата.

Ниже приведены описания некоторых полезных конечных автоматов, которые вы можете использовать в своих проектах.

Конечный автомат для пользовательского интерфейса

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

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

На рис. 5.2 представлены состояния пользовательского интерфейса нашей обучающей словарной игры для Pocket PC. Верхняя часть экрана отведена игровому полю. Персонаж перемещается по игровому полю, собирая объекты, если пользователь правильно отвечает на вопросы. На схеме представлены четыре состояния приложения, а стрелками указаны возможные переходы между состояниями пользовательского интерфейса (ПИ)

Рис. 5.2. Различные состояния пользовательского интерфейса в игре с множественным выбором

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

В дополнение к этому конечные автоматы оказываются весьма полезными во время экспериментирования с пользовательским интерфейсом и его окончательной доработки. Мы смогли очень быстро протестировать всевозможные позиционные и размерные параметры благодаря той легкости, с какой можно было изменять код компоновки элементов управления при помощи конечного автомата. Так, первоначально область вывода текста располагалась над игровым полем, но тестирование показало, что для повышения удобства пользования приложением эту область лучше разместить несколько ниже, в связи с чем она смещалась и тестировалась в самых разных конфигурациях. Кроме того, были проведены эксперименты с изменением размера текстового поля, используемого для отображения информации общего характера, представляющей интерес для пользователей, в различных состояниях приложения, в результате чего была найдена оптимальная конфигурация, обеспечивающая необходимый баланс эксплуатационных и эстетических характеристик. Хотя для выполнения описанной реорганизации пользовательского интерфейса применение конечного автомата вовсе не являлось обязательным, это намного упростило работу. Расположение всего кода, ответственного за параметры видимости, размеров и размещения, в одном месте позволяет значительно сократить сроки завершения этой части процесса итеративного проектирования, и сделать ее более понятной по сравнению с вариантом, в котором упомянутый код располагается вразброс в различных местах кода, реализующего логику приложения.

Конечный автомат для модели памяти

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

Данные, хранящиеся в памяти, часто представляют собой некий срез более крупного набора данных. В случае баз данных такие срезы, называемые также «представлениями» («view»), отражают полный или частичный результат выполнения запроса к базе данных. Поскольку пользователю почти никогда не приходится работать одновременно со всеми данными, эффективность обработки данных можно значительно повысить, удерживая в памяти только те из них, в которых пользователь нуждается в текущий момент. Пользователи хотели бы работать с ощущением, что им доступен весь набор данных, но удовлетворение этого требования вовсе не означает, что все данные обязательно должны загружаться в память одновременно.

Как и в случае пользовательских интерфейсов, существует два возможных способа управления данными — явный и неявный. Ранее в этой книге уже отмечалось, что во многих настольных приложениях прослеживается небрежное отношение к управлению используемой памятью. Это приводит к напрасному расходу ресурсов, отрицательные последствия которого отчасти компенсируются наличием на настольных компьютерах больших объемов доступной памяти и возможностью использования файлов подкачки большого размера. В случае же мобильных устройств результатом такого подхода является недопустимое снижение производительности, поскольку необходимое для эффективного выполнения приложения пространство памяти оказывается заполненным ненужными объектами. Поэтому в приложениях для мобильных устройств крайне желательно использовать более активный подход, предполагающий явное управление использованием памяти.

В соответствии с вышеизложенным, прежде чем приступать к проектированию модели использования памяти для мобильного приложения, необходимо получить ответы на следующие вопросы:


Какой объем данных должен загружаться в каждый момент времени, чтобы пользователь имел возможность работать эффективно?

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

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

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

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

■ Состав словаря. Используемый для игры словарь может содержать тысячи и даже десятки тысяч слов, каждое из которых должно снабжаться соответствующими определениями и примерами их использования. Мы могли бы попытаться загрузить в память одновременно все эти слова, но это было крайне неэкономно. Что нам необходимо — так это создать у пользователя впечатление, будто в памяти находятся сразу все слова, а на самом деле осуществлять хорошо продуманную подкачку слов в соответствие с развитием игры. Программное обеспечение должно справиться с этой задачей за счет использования гибкого конечного автомата и набора вспомогательных алгоритмов, поддерживающих создание нужной нам иллюзии. Наши алгоритмы управления памятью должны обеспечивать загрузку фиксированного числа случайных слов в память, возможность их использования в течение некоторого времени и последующее освобождение памяти для загрузки новых слов. Кроме того, желательно, чтобы проект был масштабируемым и позволял указывать количество слов, подлежащих загрузке в память, чтобы тем самым регулировать этот параметр по мере того, как мы лучше изучим потребности пользователей и возможности целевого мобильного устройства в отношении хранения этих данных в памяти. Поскольку количество слов, которые мы собираемся одновременно удерживать в памяти вместе с относящимися к ним определениями и другой родственной информацией, может исчисляться сотнями, то имеет смысл подумать о выборе наиболее подходящего способа хранения этих данных в памяти и доступа к ним.

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

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

Конечный автомат для фоновых задач

В ваших мобильных приложениях обязательно будут встречаться участки кода, которые либо долго выполняются, либо требуют сетевого доступа; в разряд «длительно выполняющихся» попадают все операции, выполнение которых может занимать более 0,5 секунды. Некоторые возможные примеры таких операций приводятся ниже:

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

■ Загрузка или сохранение больших объемов данных. Загрузка нескольких сотен порций информации из XML-файла или базы данных может занимать довольно большое время.

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

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

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

Ниже приводится пример, иллюстрирующий использование конечного автомата для управления фоновыми вычислениями, выполнение которых может занимать много времени. Целью этих вычислений является нахождение ближайшего простого числа (prime), превышающего заданное целое число. Соответствующий код может выполняться либо в синхронном режиме в целях отладки, либо в асинхронном режиме, позволяющем избежать блокирования пользовательского интерфейса на время проведения вычислений. На рис. 5.3 представлена схема простого конечного автомата, при помощи которого фоновый поток выполнения может предоставлять информацию о своем состоянии. Кроме того, этот конечный автомат позволяет потоку пользовательского интерфейса возможность направлять фоновому потоку запросы, требующие прекратить выполнение.

Рис. 5.3. Конечный автомат, предназначенный для управления выполнением фонового алгоритма нахождения простых чисел

Стиль программирования: использование операторов goto и полных путей доступа в пространствах имен

Следует дать некоторые пояснения относительно двух аспектов стиля программирования, принятого во всех примерах кодов, приводимых в данной книге.

Использование операторов goto

Вопрос о том, следует ли считать использование операторов goto в программах допустимым или же его необходимо рассматривать как признак плохого стиля программирования, является в определенной мере дискуссионным. Применимость операторов goto выступает предметом споров постольку, поскольку осуществляемая с их помощью передача управления противоречит принципам, лежащим в основе использования операторов условного перехода (if/then) и операторов циклов.

Лично я принадлежу к лагерю тех, кто считает использование операторов goto в программах вполне допустимым при условии выполнения следующих требований:

1) Им соответствует передача управления только в прямом направлении.

2) Они способствуют повышению удобочитаемости интересующих нас участков кода. Применение операторов goto может считаться непозволительным лишь в том случае, если это затрудняет понимание логики передачи управления в выполняющейся программе. Примером неудачного использования операторов goto может служить передача управления в различных направлениях, поскольку результатом этого является создание сложной системы замысловатых переходов внутри функций и трудности в отслеживании их логики; несомненно, любой из нас возражал бы против подобного использования этого оператора.

Использование полных путей доступа в пространствах имен

Возможны два способа указания типов переменных в программах:

1) В теле программы можно указывать полный путь доступа. Например, оператор System.Threading.Thread newThread; объявляет переменную newThread типа System.Threading.Thread. Достоинством таких подробных объявлений является простота их применения.

2) В начале файла с текстом программы можно задавать использование определенного пространства имен, применяя для этого ключевое слово using языка C# или ключевое слово Imports языка Visual Basic .NET. Например, если в начале файла с программой на языке C# содержится оператор using SystemThreading;, то переменная System.Threading.Thread может быть объявлена просто как Thread newThread; без указания ее полного имени.

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

На заметку! Прежде чем вы сможете использовать те или иные классы и типы в своей программе, вы должны указать, к каким сборкам (assembly), они относятся. Очень важно, чтобы вы понимали, что ключевые слова using и Imports являются всего лишь удобным синтаксическим средством и не отменяют необходимости включения ссылки на сборку. Чтобы компилятору стали известны типы, содержащиеся в сборке, вы должны явно включить соответствующую ссылку в свою программу. В Visual Studio .NET список сборок можно просмотреть с помощью элемента управления TreeView в окне проводника решений Solution Explorer. Как правило, предварительно сконфигурированные часто используемые ссылки автоматически включаются во вновь создаваемые проекты.

public class FindNextPrimeNumber

Что такое конечные автоматы

Конечный автомат — абстрактная модель, типичный паттерн в разработке компиляторов и не только. Реализовать автомат можно в любом стиле программирования — процедурном, объектно-ориентированном или функциональном.

Что такое автомат?

Будучи абстрактной моделью, автомат в коде или в схемах может стать чем угодно. Ниже показан пример диаграммы состояний для автомата, моделирующего выключатель:

У этого автомата есть:

  • два состояния (“свет выключен”, “свет включён”)
  • два перехода между этими состояниями
  • одно событие “нажали кнопку”, которое вызывает оба перехода
  • псевдопереход от чёрного кружка с заливкой, показывающий, какое состояние будет начальным. Конечного состояния здесь нет (иначе оно было бы помечено псевдопереходом к чёрному кружку без заливки)

Чуть более сложный автомат для разбора числа с плавающей точкой показан ниже:

Оба этих автомата являются детерминированными, потому что входной символ или событие однозначно определяет переход, и нет “самопроизвольных” переходов при отсутствии события. Если эти условия не соблюдаются, автомат становится недетерминированным. Также автомат не является детерминированным, если он использует дополнительную память (например, стек ранее накопленных символов) для принятия решения о переходе.

Детерминированный и недетерминированный конечные автоматы

Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние accepted либо в состояние error, что означает успешный или неуспешный разбор строки на токены соответственно.

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

Существует формальный алгоритм превращения недетерминированного автомата без дополнительной памяти в детерминированный. Кстати, подобные алгоритмы используют реализации библиотек регулярных выражений: например, для выражения «([a-z])|([a-z]\(\))» легко составить недетерминированный автомат с неоднозначными или пустыми переходами, а алгоритм позволяет превратить его в детерминированный.

Регулярное выражение в ДКА

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

  • Символ * задаёт итерацию (a.k.a. замыкание Клини)
    • Пример: “1*” ищет строки “”, “1”, “11”, …
  • Пустая строка задаёт конкатенацию двух выражений
    • Пример: “ab” ищет подстроку “ab”, “ab*” ищет подстроки вида “a”, “ab”, “abb”, …
  • Символ задаёт объединение
    • Пример: “a b c d” ищут подстроки “a”, “b”, “c”, “d”

Мы построим детерминированный конечный автомат на основе заданного регулярного выражения. Пусть дано выражение «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» , построим для него диаграмму автомата. Для наглядности обозначение начальных и конечных состояний убрано — мы считаем, что любой неожиданный символ переводит в состояние ошибки.

Преобразуем конкатенацию с (x | y*) :

Получаем промежуточный εНКА, т.е. НКА с “пустыми” — или “самопроизвольными” — переходами:

Убираем переходы по пустой цепочке ε:

Теперь состояния s3 и s5 оказались эквивалентны. Уберём s5, переименуем s6->s5, s7->s6.

Убираем неопределённые переходы из НКА:

Теперь p1 и p5 эквивалентны. Уберём p5, переименуем p6->p5, p7->p6.

Полученный автомат эквивалентен выражению «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» .

  • он допускает “aaax”
  • он не допускает “xyyb”

Применение конечных автоматов

Существует классификация программ по принципам их работы. Один из вариантов – это классификация Д. Харела, которая делит программы на три вида


  • Трансформирующие системы только трансформируют данные, то есть работают в пакетном режиме
  • Реактивные системы ещё и реагируют на команды или события
  • Интерактивные системы реагируют на команды или события и делают ответное воздействие

Автоматы применяют в трансформирующих системах, особенно связанных с обработкой текста. Примером подобной системы является интерпретатор, компилятор, шаблонизатор, или же любой простой скрипт для обработки запроса к серверу:

Что такое конечные автоматы

Конечный автомат — абстрактная модель, типичный паттерн в разработке компиляторов и не только. Реализовать автомат можно в любом стиле программирования — процедурном, объектно-ориентированном или функциональном.

Что такое автомат?

Будучи абстрактной моделью, автомат в коде или в схемах может стать чем угодно. Ниже показан пример диаграммы состояний для автомата, моделирующего выключатель:

У этого автомата есть:

  • два состояния (“свет выключен”, “свет включён”)
  • два перехода между этими состояниями
  • одно событие “нажали кнопку”, которое вызывает оба перехода
  • псевдопереход от чёрного кружка с заливкой, показывающий, какое состояние будет начальным. Конечного состояния здесь нет (иначе оно было бы помечено псевдопереходом к чёрному кружку без заливки)

Чуть более сложный автомат для разбора числа с плавающей точкой показан ниже:

Оба этих автомата являются детерминированными, потому что входной символ или событие однозначно определяет переход, и нет “самопроизвольных” переходов при отсутствии события. Если эти условия не соблюдаются, автомат становится недетерминированным. Также автомат не является детерминированным, если он использует дополнительную память (например, стек ранее накопленных символов) для принятия решения о переходе.

Детерминированный и недетерминированный конечные автоматы

Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние accepted либо в состояние error, что означает успешный или неуспешный разбор строки на токены соответственно.

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

Существует формальный алгоритм превращения недетерминированного автомата без дополнительной памяти в детерминированный. Кстати, подобные алгоритмы используют реализации библиотек регулярных выражений: например, для выражения «([a-z])|([a-z]\(\))» легко составить недетерминированный автомат с неоднозначными или пустыми переходами, а алгоритм позволяет превратить его в детерминированный.

Регулярное выражение в ДКА

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

  • Символ * задаёт итерацию (a.k.a. замыкание Клини)
    • Пример: “1*” ищет строки “”, “1”, “11”, …
  • Пустая строка задаёт конкатенацию двух выражений
    • Пример: “ab” ищет подстроку “ab”, “ab*” ищет подстроки вида “a”, “ab”, “abb”, …
  • Символ задаёт объединение
    • Пример: “a b c d” ищут подстроки “a”, “b”, “c”, “d”

Мы построим детерминированный конечный автомат на основе заданного регулярного выражения. Пусть дано выражение «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» , построим для него диаграмму автомата. Для наглядности обозначение начальных и конечных состояний убрано — мы считаем, что любой неожиданный символ переводит в состояние ошибки.

Преобразуем конкатенацию с (x | y*) :

Получаем промежуточный εНКА, т.е. НКА с “пустыми” — или “самопроизвольными” — переходами:

Убираем переходы по пустой цепочке ε:

Теперь состояния s3 и s5 оказались эквивалентны. Уберём s5, переименуем s6->s5, s7->s6.

Убираем неопределённые переходы из НКА:

Теперь p1 и p5 эквивалентны. Уберём p5, переименуем p6->p5, p7->p6.

Полученный автомат эквивалентен выражению «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» .

  • он допускает “aaax”
  • он не допускает “xyyb”

Применение конечных автоматов

Существует классификация программ по принципам их работы. Один из вариантов – это классификация Д. Харела, которая делит программы на три вида

  • Трансформирующие системы только трансформируют данные, то есть работают в пакетном режиме
  • Реактивные системы ещё и реагируют на команды или события
  • Интерактивные системы реагируют на команды или события и делают ответное воздействие

Автоматы применяют в трансформирующих системах, особенно связанных с обработкой текста. Примером подобной системы является интерпретатор, компилятор, шаблонизатор, или же любой простой скрипт для обработки запроса к серверу:

Конечные автоматы, перечисления, выражения switch

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

Например, давайте рассмотрим устройство, подобие гирлянды. Допустим мы хотим, чтобы к Arduino были подключены светодиоды, режим свечения которых можно было бы менять нажатием кнопки. Режима может быть три:

Нажимая кнопку, мы хотим переходить к очередному режиму: 1 → 2, 2 → 3, 3 → 1. Собственно точно так же, как это происходит во многих ёлочных гирляндах.

Мы не будем заниматься управлением каждым светодиодом в отдельности. Просто предположим, что все они сразу подключены к одному из пинов Arduino через MOSFET-транзистор или другой коммутатор. К какому-то другому пину при этом подключена тактовая кнопка для смены режима.

При таком раскладе, скетч, делающий всю работу, может выглядеть так:

Получилась не самая простая программа. Но и логики у нас предостаточно. Шаг за шагом разберёмся что здесь написано. Начнём с некоторых макроопределений.

Состояния

Как уже говорилось, у нас есть 3 режима: постоянное свечение, мигание, нарастание яркости. Но как их обозначать, чтобы сказать процессору какой из них текущий, какой следующий и т.п.? Как мы уже знаем, всё, с чем работает процессор — целые числа. Зная это, мы можем все возможные режимы просто пронумеровать:

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

В каждом режиме наше устройство делает что-то уникальное, отличное от того, что происходит в других режимах. Текущим может быть лишь один режим. А возможные переходы чётко определены: каждый следующий включается при нажатии кнопки. Такие системы называются конечными автоматами, а их режимы называются состояниями (англ. state).

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

Что ж, мы делаем конечный автомат — отлично. Текущее состояние, т.е. режим свечения будем хранить в переменной с именем ledState , которую изначально установим в значение STATE_SHINE . Таким образом, при включении Arduino система будет находиться в режиме постоянного свечения.

О предназначении других макроопределений и переменных поговорим по ходу дела.

Цепочка переходов между состояниями

Разберём функцию loop . А точнее, её первую часть и те определения, которые её касаются:

Первым делом мы считываем состояние кнопки в логическую переменную isButtonDown . А сразу после этого проверяем условие того, что она была нажата только что, а не находится в этом состоянии с предыдущего вызова loop . Вы могли узнать типичный приём для определения клика кнопки. Это он и есть, поэтому вызов delay и назначение wasButtonDown в конце должны быть вам понятны. Сосредоточимся на происходящем внутри условного выражения if .

Оператор равенства

В блоке кода if мы видим ещё одно, вложенное условное выражение оформленное цепочкой.

Его суть в том, чтобы установить вместо текущего состояния следующее. С помощью условий определяется текущее состояние, а в коде веткок устанавливается соответствующее следующее состояние.

Обратите внимание, что в C++ проверка на равенство осуществляется символом == , т.е. двойным знаком равенства. Так записывается оператор «равно». Значение логического выражения будет истинным, если значения слева и справа от == равны.

Типичная ошибка при программировании — перепутать оператор равенства == с оператором присваивания = . Если написать:

программа будет абсолютно корректна с точки зрения компилятора C++, но происходить будет совсем не то, что предполагается: сначала переменной ledState будет присвоено значение STATE_SHINE , а только затем будет проверенно истинно ли её значение.

Поэтому, например, в нашем случае, если бы мы допустили такую ошибку, при прохождении этого кода ledState всегда бы перезаписывалась значением STATE_SHINE , которое в свою очередь объявлено как 0 , 0 в условии эквивалентен false , а следовательно внутрь блока кода мы бы никогда не попали.

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


Своя логика в каждом состоянии

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

Рассмотрим вторую половину кода функции loop и определения, которые в ней используются.

В теле loop мы видим цепочку условных выражений, где в каждом из условий мы сравниваем текущее состояние ledState поочерёдно со всеми возможными. Суть точно та же, что и была ранее, при переключении состояний по нажатию кнопки: в зависимости от текущего значения ledState исполнить тот или иной блок кода.

В приведённом коде можно отчётливо увидеть 3 блока кода: по одному на каждый режим свечения. Первый из них исполняется в случае, если ledState равно STATE_SHINE , т.е. если текущий режим — непрерывное свечение. Блок кода в этом случае примитивен, нам просто нужно убедиться, что светодиоды включены:

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

Режим мигания

Дальше интереснее. Если текущее состояние было установлена в STATE_BLINK , т.е. режим мигания каждые 2 секунды, выполняется ветка с кодом:

Вы знаете, что для того, чтобы просто помигать светодиодом на Arduino достаточно последовательно вызывать digitalWrite и delay , то включая, то выключая пин:

Но мы поступили иначе и несколько сложнее. Зачем?

Дело в том, что вызов delay приводит к усыплению процессора, и он просто «застывает» на вызове на указанный промежуток времени. Он не сможет заниматься ничем другим, кроме как спать. А теперь вспомним, что наша гирлянда всегда «одновременно» делает 2 вещи:

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

Как решить проблему? Не использовать delay вовсе! Вместо этого, мы каждый раз попадая в нашу ветку можем заново рассчитывать: должна ли гирлянда быть включена или выключена именно в текущий момент времени.

Для этого мы используем небольшое арифметическое выражение: (millis() / BLINK_DELAY) % 2 .

Встроенная функция millis просто возвращает значение равное количеству милисекунд, прошедших с момента включения или перезагрузки Arduino. Мы используем целочисленное деление её результата на BLINK_DELAY , которое мы в свою очередь определили как 2000 , т.е. 2000 миллисекунд.

Таким образом значение millis() / BLINK_DELAY будет увеличиваться на единицу всякий раз, когда с момента старта Arduino пройдут очередные 2000 мс, т.е. 2 секунды.

Далее мы просто берём остаток от деления на 2 этого промежуточного результата на. Таким образом, итоговое значение будет то 0 , то 1 , переключаясь каждые 2 секунды. То, что нам нужно! И мы просто передаём вычисленное значение в качестве аргумента при вызове digitalWrite :

Режим нарастания яркости

Если текущее состояние нашей гирлянды — STATE_FADE , будет исполняться третий блок, который заставит светодиоды плавно набирать свою яркость в течение 10 секунд, гаснуть и набирать яркость снова:

Суть примерно та же, что и для мигания. Просто мы используем немного другое выражение для расчётов и вызываем analogWrite вместо digitalWrite .

Наша задача: заставить светодиоды набирать яркость от нуля до максимума ровно за 10 секунд или, что то же самое, 10000 миллисекунд. Функция analogWrite в качестве параметра яркости принимает значения от 0 до 255, т.е. всего 256 градаций. Поэтому, для увеличения яркости на одну градацию должно пройти 10000 мс ÷ 256 ≈ 39 мс. Именно эти значения мы определили в начале программы:

Так значение выражения millis() / FADE_STEP_DELAY будет становиться на единицу больше каждый раз, когда проходит 39 мс.

Обратите внимание на скобки в определении FADE_STEP_DELAY . Поскольку значения макроопределений подставляются в программу как есть, мы получаем millis() / (10000 / 256) ; а если скобок бы не было, получилось бы millis() / 10000 / 256 , что совершенно не одно и то же с точки зрения математики. Поэтому добавляйте круглые скобки вокруг любых арифметических выражений, когда используете их в качестве значений макроопределений.

Наконец, от промежуточного значения millis() / FADE_STEP_DELAY мы получаем остаток деления на 256 . Таким образом, всё будет начинаться сначала всякий раз, когда промежуточное значение будет становиться кратным 256. То, что нужно!

Арифметика состояний

Ещё раз взглянем на код, который обеспечивал нам включение очередного состояния при клике кнопки:

Если бы состояний у нас было не 3, а 33, код бы растянулся на много строк, но при этом ничего нового и уникального в программу бы не добавлял: он бы оставался однотипным. Если вам при написании скетча кажется, что какие-то его места сводятся к монотонному набору инструкций, слабо отличающихся друг от друга, почти наверняка существует способ упростить этот код, сделать его проще, понятнее, компактнее. Стоит лишь подумать.

Что можно сделать с нашей цепочкой? Вспомним, что состояния для процессора — это всего лишь целые числа. Мы определили их с помощью макроопределений.

Эти числа мы определили последовательно. Поэтому переключение ledState на очередное значение — это ни что иное, как прибавление единицы. Единственная загвоздка — переход из последнего состояния в первое. Но нам уже знаком оператор остатка от деления, а с помощью него легко учесть этот сценарий. Тогда весь код для включения следующего состояния можно написать без всякого ветвления так:

Где TOTAL_STATES — общее количество состояний, которое мы можем определить как:

Перечисления enum

Задача перечисления состояний и присвоение им последовательных целых значений довольно распространённая. Для подобных случаев, чтобы чуть упростить работу и повысить читаемость программы, в C++ существуют так называемые перечисления (англ. enumeration). Для объявления нового перечисления используется конструкция:

С точки зрения компиляции это ничем не отличается от:

Но в случае с enum нам не пришлось явно прописывать значения 0, 1, 2, 3 и т.д. В перечислениях, первая константа автоматически получает значение 0, а каждая следующая на единицу больше.

И чем ещё хорошо перечисление: мы можем использовать его имя ( State в нашем случае) в качестве типа данных, так же как int , bool и т.п. То есть мы можем определить переменную текущего состояния так:

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

Собрав всё вместе, получим обновлённый вариант нашей программы:

Выражение выбора switch

Для того, чтобы понять что делать со светодиодами гирлянды в данный конкретный момент мы использовали цепочку из выражений if , где поочерёдно сравнивали ledState со всеми возможными состояниями. Это довольно распространённый сценарий и для него в C++ существует выражение выбора switch . Мы можем использовать его для нашей цели:

Не сказать, что код стал компактнее, но он стал чуть нагляднее.

Суть выражения switch такова. Сначала вычисляется значение арифметического выражения, записанного в круглых скобках. В нашем случае — это просто получение значения ledState . Затем, в блоке кода между фигурными скобками ищется метка case , чьё значение равно вычисленному. Исполнение кода начинается с неё и идёт последовательно до конца блока (не до следующего case ). Исполнение блока можно завершить досрочно выражением break .

Частая ошибка от невнимательности — забыть поставить break . В этом случае процессор выполнит код, принадлежащий другим меткам, а это чаще всего — не то, что нужно. Да, это неприятная особенность C++, но так уж сложилась история. Изначально это было сделано для того, чтобы можно было перечислить сразу несколько значений на одну ветку. Например, если бы для состояний STATE_FADE и STATE_BLINK мы, по задумке, должны бы были делать одно и то же, мы могли бы написать:

Также в switch , на последнем месте можно указать метку со специальным именем default . Она будет выполнена, если ни одна другая метка case не подошла по значению.

Итак, вы познакомились с конечными автоматами, состояниями, переходами, принципами одновременного выполнения нескольких задач. В нашем примере, для разных состояний мы использовали довольно простую логику: один вызов digitalWrite с нехитрым арифметическим выражением; а для переключения состояний и вовсе использовали последовательные переходы по клику кнопки.

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

Так же, как и со всем остальным, ничто не мешает делать вложенные конечные автоматы: то есть состояния, которые сами по себе являются конечными автоматами. Главное поддерживать код стройным и читаемым, тогда у вас всё получится!

Основы теории конечных автоматов.

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

1) Функциональные преобразователи

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

2) Автоматы, в которых результат преобразования информации, поступающей на вход, зависит не только от того, какая информация появилась на входе, но и от того, какая информация поступала на эти автоматы раньше. Такие устройства называются конечными автоматами или автоматами с памятью (примерами таких устройств являются биологические системы). На один и тот же входной сигнал конечный автомат (КА) может реагировать по-разному, в зависимости от того, в каком состоянии он находится в данный момент.

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

Число входных историй любого конечного автомата бесконечно, но счетно. Если автомат будет вести себя по-разному для каждой возможной предыстории, то он должен иметь бесконечный ресурс (память), чтобы все эти предыстории как-то фиксировать. Если ввести на множестве предысторий —- то две предыстории можно считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автоматам достаточно запоминать класс эквивалентности, к которому принадлежит предыстория. В случае, когда таких классов эквивалентности конечное число, является простейшим, но именно такая математическая модель представляет большую практическую ценность и получила широкое распространение. Соответствующая формальная модель и называется конечными автоматами.

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

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

Основные понятия и определения конечных автоматов

Конечным автоматом (автоматом Милли) называется математическая модель, состоящая из 5 элементов: (S,X,Y, δ, λ), где:

S — конечное множество состояний k>;

X — конечный входной алфавит;

Y — конечный выходной алфавит;

δ: S x X -> S — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние;

λ: S х X -> Y — функция выхода, отображающая текущее состояние и текущий вход в выходной символ.

Если в конечном автомате выделено специальное начальное состояние S, то этот автомат называется инициальным.

Два конечных автомата А1 и А2 эквивалентны, если реализуемые ими отображения вход-выход – эквивалентны. Две логические функции f1 и f2 эквивалентны, если на всех наборах аргументов они имеют одинаковые значения, т.к. число аргументов логической функции конечно, то достаточно сравнить значение этих функций на всех наборах аргументов. Конечный автомат реализует бесконечное множество входных последовательностей сигналов в конечное множество выходных сигналов, поэтому автоматные отображения вход->выход, нельзя определить простым перечислением их отображений и сравнить их значения на всех бесконечных множествах. Для того, чтобы определить эквивалентность автоматов необходимо расширить функции так, чтобы функции переходов и выходов были определены на множествах последовательностей сигналов входного алфавита (последовательных цепочках) элементов х.

Определение 2.3 Пусть A= — конечный автомат. Расширенными функциями перехода и выхода автомата А называются функции

d*: S x X* ® S и l* : S x X*® Y*, определенные так :


(e — пустая цепочка, альфа – сама цепочка

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

Другими словами, для данного автомата А и его функций dА и lА могут быть определены не только на множестве X всех его входных букв, но и на множестве X* всех входных слов. Для любого входного слова

Это традиционное определение с многоточиями, намного точнее и лучше читается, чем индуктивное определение.

Функция переходов задается:

а) d(Si ,aj) задается автоматной таблицей;

б) для любого слова aÎX* и любой буквы aj

С помощью расширенной функции δ определяется (также индуктивно) расширенная функция λ :

λ ( S , αa )= λ( δ * ( S , α)a )(2-4)

Зафиксируем в автомате А начальное состояние S и каждому слову α=aj aj . a поставим в соответствие слово ω выходном алфавите У:

где Ù- операция конкатенации.

Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным (или ограниченно детерминированным) оператором. Если результатом применения автоматного оператора к входному слову α является выходное слово ω, то это будем обозначать соответственно A(S ,α)=ω или A(α)=ω, причем |α|=|ω| или l(α)=l(ω), т.е. слова α и ω имеют одинаковую длину.

Автоматное отображение обладает двумя свойствами, которые непосредственно следуют из (2-5): слова a и w имеют одинаковую длину (свойство сохранения длины) и, кроме того, автоматные операторы – это операторы без предвосхищения, т.е. операторы, которые, перерабатывая слово слева направо, не заглядывают вперед. Это свойство отражает тот факт, что i-тая буква выходного слова зависит только от первых i букв входного слова.

Определение 2.4 Пусть А= — конечный автомат. Состояние S є S называется достижимым тогда и только тогда, когда ( α∈X ) δ ( S , α)= S (то есть под воздействием какой-либо цепочки входных сигналов автомат попадает в это состояние ). Состояние конечного автомата является недостижимым тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние: Недостижимо (S ) ( α∈X ) δ ( S , α) S .

Определение 2.5 Автомат А называется сильно связным, если из любого его состояния достижимо любое другое состояние.

Определение 2.6 Автомат называется автономным, если его входной алфавит состоит из одной буквы X=.

Определение 2.7 Автомат называется частичным или не полностью определенным, если хотя бы одна из двух функций не полностью определена. В таком автомате для некоторых пар (состояние – вход, состояние – выход) значения функций δ или λ не определены. В автоматной таблице неполная определенность автомата выражается в том, что некоторые её клетки не заполнены.

Определение 2.8Конечные автоматы А= и B = называются эквивалентными, если выполнены два условия:

а) их входные алфавиты совпадают X =X =X;

б) реализуемые ими отображения совпадают: ( αÎX ) λ ( S , α)=λ ( S ,α).

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

Определение 2.9 Прямым произведениемконечных автоматов А= и B= с одинаковым входным алфавитом X (обозначается AxB ) называется автомат:

а) ( S Î S )( S Î S )( x ÎX) δ (( S ,S ),x)= (δ ( S ,x), δ (S ,x));

б) ( S Î S )( S ÎS )( x ÎX) λ (( S ,S ),x)= (λ ( S ,x), λ (S ,x)).

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

14.Способы задания конечных автоматов.

Устройство, оперирующие с логическими сигналами, принимающее только 2 значения – 0 и 1и имеющее некоторое множество внутренних эквивалентных состояний S, множество входных сигналом x и множество выходных сигналов y – называется цифровым автоматом.

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

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

Если в течении времени не произошло изменений входных сигналов x и соответственно внутренних состояний S.

Различают автоматы Мура и автоматы Милли.

Автомат Мура является частным случаем более широкого понятия – автомата Мили.

Автоматы Мура описываются следующими функциями переходов и выходов:

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

Автоматы Мили отличаются от автоматов Мура тем, что выходной сигнал в этом автомате зависит не только от состояния, но и от входного сигнала.

Si+1 = f(Si, xi+1) yi+1 = y(si, xi+1)

Понятие внутреннего состояния автомата предполагает наличие у автомата внутренней памяти. Число различных эквивалентных состояний зависит от глубины памяти.

В качестве элементов памяти могут использоваться стандартные модули ПЗУ или логические схемы с обратными связями в частности – различные типы триггеров.

В принципе любой автомат Мура можно свести к автомату Мили и наоборот.

Автомат Мили – более универсальное устройство

У автомата Мили нет таких ограничений, которые есть у Мура

Задав множество (x s y) достаточно трудно определить как работает конечный автомат. Приведенные выше уравнения, описывающие функционирование автоматов мура и мили устанавливают связь между множествами x s y, но они неудобны для описания функционирования конкретных автоматов, поэтому на практике получили распространение другие способы описания работы конечных автоматов.

Наиболее широко распространены табличное задание, где заданы таблицы переходов и выходов конечного автомата. Здание конечного в виде граф-схемы, а так же задание конечных автоматов в виде ЛГСА (логическая схема алгоритмов).

Рассмотрим задание КА, который для любой пары чисел, записанных в двоичной системе счисления вычисляет и выводит их сумму, при этом данные начинаются с битов, имеющие наименьшие разряды и числа читаются справа-налево.

(в билетах будет пример с триггерами, RS и другие)

X\S S0 S1
S0 S0
S0 S1
S0 S1
S1 S1

Таблица выходной функции 2.2

X\S S0 S1

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

Входные сигналы в упорядоченном виде записаны в первом столбце.

На пересечении строк и столбцов получаем клетку в которой записано новое состояние.

Таблица переходов (2.1) может быть определена неполностью. В этом случае в таблице имеются прочерки в отдельных клетках.

Некоторые сигналы не вызывают изменения состояния. Так, под действием входных сигналов 0 и 1автомат сохраняет состояние S0, Если он в нем находился и состояние S1, если при подаче такой комбинации входных сигналов он находился в состоянии S1.

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

Значения выходного сиг нала автомата приведено в таблице 2.2

Иногда, если имеется такая возможность – обе таблицы совмещают.

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

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

Распространенное средство описания автомата – логическая граф-схема описания алгоритма.

15. Конечный автомат как модель «реагирующей системы».

Последнее время для программистов, работающих в области информатики, стала ясна необходимость выделения особого класса систем, который был назван реагирующими системами. Эти системы способны реагировать на поток внешних событий. Оказалось, что математическая модель конечного автомата является удобным средством описания таких систем. Удобство применения математической модели конечного автомата состоит в том, что эта модель обладает ясностью семантики, наглядностью и выразительностью и в то же время она достаточно строга и формальна.

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

Простым и достаточно эффективным расширением модели классического конечного автомата является введение понятия «внешнее событие», наступление которого можно считать условием перехода автомата в новое состояние. Такими событиями можно считать получение сигнала на вход автомата, прерывание и срабатывание таймера. Со срабатыванием таймера естественно связывается понятие времени в автомате. Действительно, введением понятия времени в конечном автомате можно связать с ограничением пребывания автомата в заранее заданном, конкретном состоянии. Такое ограничение, если оно необходимо, лучше всего задавать таймером математической модели конечного автомата, срабатывание таймера должно вызывать переход автомата в другое состояние. Рассмотрим в качестве примера спецификацию процесса, определяющего одинарный или двойной щелчок мыши. Напомним, что двойным щелчком считается последовательность из 2-х нажатий клавиши, разделяемая промежутком времени t=250мс. Представим граф переходов конечного автомата, решающего эту задачу.

По первому щелчку мыши (клик) автомат переходит из состояния S в состояние S1, и если до истечения следующих t=250мс на вход поступает еще один сигнал (событие клик), то на выход будет выдан сигнал click\double в противном случае t\click. В любом из этих вариантов автомат возвращается в положение S и работа автомата повторяется.

16. Конечный автомат как модель протокола передачи сообщений в сетях.

Последнее изменение этой страницы: 2020-08-01; Нарушение авторского права страницы

Илон Маск рекомендует:  Автоматизация бэкапа БД с помощью mysqldump
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL