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

Лекция 5.

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

Дискретно-детерминированные модели (F -схемы)

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F -схему ), характеризующуюся шестью элементами: конечным множеством Х входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z 0 , z 0 Î Z ; функцией переходов j(z , x ); функцией выходов y(z , x ). Автомат, задаваемый F -схемой: F = áZ , X , Y , y, j, z 0 ñ, функционирует в дискретном времени, моментами которого являются такты, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t -му такту при t = 0, 1, 2, …, через z (t ), x (t ), y (t ). При этом по условию z (0) = z 0 , а z (t )ÎZ , x (t )ÎX , y (t )ÎY .

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

Входной алфавит: "антилопа", "охотник".

Внутренние состояния: "сытый", "голодный".

Выходной алфавит: "съесть", "спать", "убежать"

Таблица переходов:

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, … дискретного времени F -автомат находится в определенном состоянии z (t ) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z (0) = z 0 . В момент t , будучи в состоянии z (t ), автомат способен воспринять на входном канале сигнал x (t )ÎX и выдать на выходном канале сигнал y (t ) = y[z (t ), x (t )], переходя в состояние z(t +1) = j[z (t ), x (t )], z (t )Î Z , y (t )ÎY . Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y . Другими словами, если на вход конечного автомата, установленного в начальное состояние z 0 , подавать в некоторой последовательности буквы входного алфавита x (0), x (1), x (2), …, т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y (0), y (1), y (2), …, образуя выходное слово.

Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t -м такте на вход автомата, находящегося в состоянии z (t ), подается некоторый сигнал x (t ), на который он реагирует переходом (t +1)-го такта в новое состояние z (t +1) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для F -автомата первого рода, называемого также автоматом Мили ,

z (t +1) = j[z (t ), x (t )], t = 0, 1, 2, …; (2.15)

y (t ) = y[z (t ), x (t )], t = 0, 1, 2, …; (2.16)

для F -автомата второго рода

z (t +1) = j[z (t ), x (t )], t = 0, 1, 2, …; (2.17)

y (t ) = y[z (t ), x (t – 1)], t = 1, 2, 3,…. (2.18)

Автомат второго рода, для которого

y (t ) = y[z (t )], t = 0, 1, 2, …, (2.19)

т.е. функция выхода не зависит от входной переменной x (t ), называется автоматом Мура .

Таким образом, уравнения (2.15)-(2.19), полностью задающие
F -автомат, являются частным случаем уравнений (2.3) и (2.4), когда
система S – детерминированная и на её единственный вход поступает дискретный сигнал X .

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

y (t ) = y[ x (t )], t = 0, 1, 2, … .

Эта функция называется булевой, если алфавит X и Y , которым принадлежат значения сигналов x и y , состоят из двух букв.

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных F -автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учетом «считанного» и в соответствии с уравнениями (2.15)-(2.19) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Таким образом, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами. Асинхронный F -автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины x , он может, как следует из (2.15)-(2.19), несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое, которое уже не может быть изменено данным входным сигналом.

Возможные приложения F -схемы. Чтобы задать конечный F -автомат, необходимо описать все элементы множества F = <Z , X , Y , y, j, z 0 >, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z 0 , в котором автомат находится в состоянии t = 0. Существуют несколько способов задания работы F -автоматов, но наиболее часто используются табличный, графический и матричный.

В табличном способе задаются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый слева столбец соответствует начальному состоянию z 0 . На пересечении i -й строки и k -го столбца таблицы переходов помещается соответствующее значение j(z k , x i ) функции переходов, а в таблице выходов – соответствующее значение y(z k , x i ) функции выходов. Для F -автомата Мура обе таблицы можно совместить.

Описание работы F -автомата Мили таблицами переходов j и выходов y иллюстрируется табл. 2.1, а описание F -автомата Мура – таблицей переходов (табл. 2.2).

Таблица 2.1



Переходы
	j(z 0 , x 1)	j(z 1 , x 1)	j(z k , x 1)
	j(z 0 , x 2)	j(z 1 , x 2)	j(z k , x 2)

	j(z 0 , x i )	j(z 1 , x i )	j(z k , x i )
Выходы
	y(z 0 , x 1)	y(z 1 , x 1)	y(z k , x 1)
	y(z 0 , x 2)	y(z 1 , x 2)	y(z k , x 2)

	y(z 0 , x i )	y(z 1 , x i )	y(z k , x i )

Таблица 2.2




j(z 0 , x 1)	j(z 1 , x 1)	j(z k , x 1)
j(z 0 , x 2)	j(z 1 , x 2)	j(z k , x 2)

j(z 0 , x i )	j(z 1 , x i )	j(z k , x i )

Примеры табличного способа задания F -автомата Мили F 1 приведены в табл. 2.3, а для F -автомата Мура F 2 – в табл. 2.4.

Таблица 2.3



Переходы


Выходы

Таблица 2.4

При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x k вызывает переход из состояния z i в состояние z j , то на графе автомата дуга, соединяющая вершину z i c вершиной z j , обозначается x k . Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал x k действует на состояние z i , то получается дуга, исходящая из z i и помеченная x k ; эту дугу дополнительно отмечают выходным сигналом y = y(z i , x k ). Для автомата Мура аналогичная разметка графа такова: если входной сигнал x k , действуя на некоторое состояние автомата, вызывает переход в состояние z j , то дугу, направленную в z i и помеченную x k , дополнительно отмечают выходным
сигналом y = y(z j , x k ).

На рис. 2.4. а , б приведены заданные ранее таблицами F -автоматы Мили F 1 и Мура F 2 соответственно.

Рис. 2.4. Графы автоматов а – Мили и б – Мура

При матричном задании конечного автомата матрица соединений автомата квадратная С =||с ij ||, строки соответствуют исходным состояниям, а столбцы – состояния перехода. Элемент с ij = x k /y s , стоящий на пересечении
i -й строки и j -го столбца, в случае автомата Мили соответствует входному сигналу x k , вызывающему переход из состояния z i в состояние z j , и выходному сигналу y s , выдаваемому при этом переходе. Для автомата Мили F 1, рассмотренного выше, матрица соединений имеет вид:

x 2 / y 1 – x 1 / y 1

C 1 = x 1 / y 1 – x 2 / y 2 .

x 1 / y 2 x 2 /y 1 –

Для F -автомата Мура элемент с ij равен множеству входных сигналов на переходе (z i , z j ), а выход описывается вектором выходов

= y(z k ) ,

i -я компонента которого – выходной сигнал, отмечающий состояние z i .

Для рассмотренного выше F -автомата Мура F2 матрицы соединений и вектор выходов имеют вид:

– x 1 – x 2 – у 1

– x 2 – – x 1 у 1

C 2 = – x 2 – – x 1 ; = у 3

x 2 – x 1 – – у 2

x 2 – x 1 – – у 3

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

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

Пример моделирования с помощью конечных автоматов

Пример построения конечного автомата (процессора)

для распознавания и обработки записи вещественных чисел

На входе автомата: строка символов, представляющая вещественное число без знака.

На выходе автомата: пара целых чисел: мантисса и порядок или сообщение об ошибке, если число записано неправильно.

Пример.

1. 38.71 Е - 42 → (3871, -44);

2. .9 Е 21 → (9, 20);

3. 4.5.6 .9 → Ошибка;

4. 3. Е 4 → (3, 4);

5. 12 → (12, 0);

6. 1.2 → (12, -1).

На данном примере покажем образец для решения задачи о построении конечного распознающего автомата и обрабатывающего процессора. Разобьем этот процесс на несколько этапов.

1. Выписать один или несколько примеров характерных цепочек, на основе которых:

а) определить входной алфавит;

б) подписать под символами цепочек состояния, моделируя работу автомата;

в) выписать словесные описания состояний.

а) Входной алфавит A ={ц Е. + -}; (где ц – цифра 0..9)

б) Примеры.

Входная цепочка: 3 8 . 7 1 Е – 4 2

Состояния автомата: Ø 1 1 2 3 3 4 5 6 6

Входная цепочка: . 9 Е 2 1.

Состояния автомата: Ø7 3 4 6 6.

в) Ø начальное состояние; ожидание цифры мантиссы, либо точки.

1 – прочитана цифра первой части мантиссы; ожидание еще одной цифры или точки, или символа Е.

2 – прочитана точка; ожидание цифры дробной части или символа Е.

3 – прочитана цифра дробной части мантиссы; ожидание еще одной цифры или символа Е.

4 – прочитан символ Е; ожидание знаков операций +, -, или цифры порядка.

5 – прочитан знак порядка; ожидание цифры порядка.

6 – прочитана цифра порядка; ожидание еще одной цифры.

7 – прочитана точка в качестве 1-го символа входной цепочки; ожидание обязательной цифры дробной части мантиссы.

Е r - состояние ошибки.

2. Построить схему и таблицу переходов конечного автомата.

Все неотмеченные стрелками переходы ведут в состояние ошибки Er.

					Допустимость








Е r

Здесь все пустые клетки соответствуют переходу в состояние ошибки Er.

3. Привести полученный автомат к минимальному виду.

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

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

Для удобства дальнейшего описания переименуем состояния следующим образом:

Ниже приведена новая диаграмма и таблица переходов конечного автомата.

Новая таблица переходов:








Е r

Таблица вызова процедур процессора:

	2 a		7 a
	2 b	4 a	3 a
	3 b	4 b
	6 a			5 a
	6 b
	6 c
	3 c
Е r

4. Построить процессор, обрабатывающий символ конца строки.

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

5. Дополнить переходы процессора именами процедур.

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

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

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

Число – регистр значащей части числа (целое число).

Порядок – регистр порядка (целое число).

Счетчик – регистр счетчика цифр, стоящих после (целое число).

Знак - (±1) – знак порядка.

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

2а: Число := ц

2в: Число := 10 * Число + ц

3а: Счетчик := 0

3в: Счетчик := Счетчик + 1

Число := 10 * Число + ц

3с: Число := ц; Счетчик =: 1

4а: Счетчик =: 0

5а: Знак := {+1, если а=’+’ или -1, если a=’-‘} (здесь а – входной символ.)

6а: Знак := +1

Порядок := ц

6в: Порядок := ц

6с: Порядок := 10 * Порядок + ц

Да1: Порядок := 0

Да2: Порядок := -Счетчик

Да3: Порядок := Знак * Порядок - Счетчик

Здесь символом Æ обозначено отсутствие всякого действия – пустая процедура. В тех случаях, когда целочисленному регистру присваивается символ (например: Счетчик =ц), подразумеваем неявное преобразование символа цифры в число им обозначаемое.

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

В качестве примеров рассмотрим работу автомата по обработке следующих трёх входных цепочек. В скобках указано ожидаемое значение регистров Число и Порядок на выходе процессора.

а) 67.89E-12┤ (6789, -14)

б) 2E3┤ (2,3)

в) .89┤ (3,-1)

Входной символ	Переход в сост., процедура	Значения регистров
Входной символ	Переход в сост., процедура	Число	Порядок	Счетчик	Знак
	1 (начальное)
		6
		67
		67		0
		*678*		1
		*6789*		2

					-1


		*6789*	*-14*
	1 (начальное)
		2
				0
			3		+1
		2	3
	1 (начальное)

		8		1
		89
		89	-2

Результат работы автомата определяется по его конечному состоянию.

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

Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов ) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф , вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов - табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу - один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

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

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

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: , где:

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .

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

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

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет - так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Специализированные языки программирования

Язык последовательных функциональных схем SFC (Sequential Function Chart) - графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

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

Разработка моделей с использованием конечных автоматов

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

Примечания

См. также

Секвенциальная логика (Последовательностная логика)

Ссылки

Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - М.: ВИНИТИ, 1976. - Т. 13. - С. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Применение конечных автоматов для решения задач автоматизации
Пример реализации конечного автомата на языке Python для фреймворка Django

Wikimedia Foundation . 2010 .

Кейнс, Джон Мейнард
Диаграмма состояний (теория автоматов)

Смотреть что такое "Конечный автомат" в других словарях:

конечный автомат - КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. конечный автомат Спецификация последовательности… …

Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: Finite state machine См … Финансовый словарь

конечный автомат - baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas

КОНЕЧНЫЙ АВТОМАТ - автомат, у к рого множество состояний, а также множество входных и выходных сигналов являются конечными. К. а. может быть моделью технич. устройства (ЭВМ, релейное устройство) либо биол. системы (идеализир. нервная система животного). Важными… … Большой энциклопедический политехнический словарь

конечный автомат в модульном исполнении - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite modular automaton … Справочник технического переводчика

конечный автомат доступности - (МСЭ Т Y.1711). Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика

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

детерминированный конечный автомат - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика

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

Результат работы автомата определяется по его конечному состоянию.

Другие способы описания

Диаграмма состояний (или иногда граф переходов ) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф , вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов - табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу - один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

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

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

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: , где:

Автоматы и регулярные языки

Специализированные языки программирования

Язык последовательных функциональных схем SFC (Sequential Function Chart) - графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

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

Разработка моделей с использованием конечных автоматов

Примечания

См. также

Секвенциальная логика (Последовательностная логика)

Ссылки

Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - М.: ВИНИТИ, 1976. - Т. 13. - С. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Применение конечных автоматов для решения задач автоматизации
Пример реализации конечного автомата на языке Python для фреймворка Django

Wikimedia Foundation . 2010 .

Кейнс, Джон Мейнард
Диаграмма состояний (теория автоматов)

Смотреть что такое "Конечный автомат" в других словарях:

В статье рассмотрены простые конечные автоматы и их реализация на C++ с помощью switch-конструкций, таблиц времени исполнения и библиотеки Boost Statechart .

Введение

Грубо говоря, конечный автомат (Finite State Machine), глазами пользователя – это черный ящик, в который можно что-то передать и что-то оттуда получить. Это очень удобная абстракция, которая позволяет скрыть сложный алгоритм, кроме того конечные автоматы очень эффективны.

Конечные автоматы изображают в виде диаграмм состоящих из состояний и переходов. Поясню на простом примере:

Как вы наверное догадались – это диаграмма состояний лампочки. Начальное состояние обозначается черным кружком, переходы стрелками, некоторые стрелки подписаны – это события после которых автомат переходит в другое состояние. Итак, сразу из начального состояния, мы попадаем в состояние Light Off – лампа не горит. Если нажать кнопку, то автомат изменит свое состояние и перейдет по стрелке помеченной Push Button , в состояние Light On – лампа горит. Перейти из этого состояния можно опять же по стрелке, после нажатия кнопки, в состояние Light Off .

Также широко используются таблицы переходов:

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

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

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

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

Рассмотрим диаграмму:

Из начального состояния мы попадаем в состояние Start . Проверяем текущий символ, и если он является буквой, то переходим в состояние Word по стрелке помеченной как Letter . Это состояние предполагает, что в данный момент мы рассматриваем слово, анализ дальнейших символов, либо подтвердит данное предположение, либо опровергнет. Итак, рассматриваем следующий символ, если он является буквой, то состояние не изменяется (обратите внимание на круговую стрелку помеченную как Letter ). Если символ не является буквой, а соответствует пробельному символу, то это означает, что предположение было верным и мы обнаружили слово (делаем переход по стрелке Space в состояние Start ). Если символ не является, ни буквой, ни пробелом, значит мы ошиблись в предположении и последовательность которую мы рассматриваем, не является словом (переходим по стрелке Unknown в состояние Skip ).

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

После перехода в состояние Start , поиск цикл повторяется с начала. Ветвь с распознаванием чисел аналогична ветви распознавания слов.

Автомат с использованием switch-инструкций

Первое – возможные состояния:

После чего мы итерируем по строке подсовывая автомату текущий символ. Сам автомат представляет собой инструкцию switch сначала выполняющей переход в секцию текущего состояния. Внутри секции есть конструкция if-else, которая в зависимости от события (пришедшего символа) изменяет текущее состояние:

const size_t length = text.length () ; for (size_t i = 0 ; i ! = length; ++ i) { const char current = text[ i] ; switch (state) { case State_Start: if (std:: isdigit (current) ) { state = State_Number; } else if (std:: isalpha (current) ) { state = State_Word; } break ; case State_Number: if (std:: isspace (current) ) {

Здесь смотрим на диаграмму – текущее состояние Number , событие Space (встречен пробельный символ), а значит найдено число:

FoundNumber() ; state = State_Start; } else if (! std:: isdigit (current) ) { state = State_Skip; } break ; case State_Word: if (std:: isspace (current) ) { FoundWord() ; state = State_Start; } else if (! std:: isalpha (current) ) { state = State_Skip; } break ; case State_Skip: if (std:: isspace (current) ) { state = State_Start; } break ; } }

Итог:

Высокая эффективность

Простота реализации для простых алгоритмов

— Тяжело поддерживать

Интерпретация времени выполнения

Идея данного подхода проста – надо создать таблицу переходов, заполнить ее, и потом, при наступлении события, найди в таблице следующее состояние и сделать переход:

enum Events { Event_Space, Event_Digit, Event_Letter, Event_Unknown } ; void ProcessEvent(Events event) ; ... struct Transition { States BaseState_; Events Event_; States TargetState_; } ; void AddTransition(States fromState, Events event, States toState) ; ... typedef std:: vector < transition> TransitionTable; TransitionTable Transitions_; States CurrentState_;

Заполнение таблицы:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

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

Чтобы автомат, при наступлении некоторых событий, мог оповестить некоторый код, можно добавить в структуру с информацией о переходе (Transition ) указатель на функцию (Action ), которая будет вызываться:

typedef void (DynamicMachine:: * Action) () ; struct Transition { States BaseState_; Events Event_; States TargetState_; Action Action_; } ; ... void AddTransition(States fromState, Events event, States toState, Action action) ; ... AddTransition (State_Number, Event_Space, State_Start, & DynamicMachine:: FoundNumber ) ;

Итог:

Гибкость и наглядность

Проще поддерживать

— Меньшая производительность по сравнению с switch-блоками

Интерпретация времени исполнения. Оптимизация по скорости

Можно ли объединить наглядность со скоростью? Сделать автомат настолько же эффективным, как автомат на switch-блоках вряд ли удастся, но сократить разрыв можно. Для этого надо из таблицы, построить матрицу, такую, чтобы для получения информации о переходе не выполнять поиск, а сделать выборку по номеру состояния и события:

Достигается результат, за счет расхода памяти.

Итог:

Гибкость, наглядность

Эффективен

— Расход памяти (скорее всего несущественно)

Boost Statechart

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

Итак, сначала определим события:

namespace Events { struct Digit : boost:: statechart :: event < Digit> { } ; struct Letter : boost:: statechart :: event < Letter> { } ; struct Space : boost:: statechart :: event < Space> { } ; struct Unknown : boost:: statechart :: event < Unknown> { } ; }

Саму машину (обратите внимание, что второй параметр шаблона – начальное состояние):

struct Machine : boost:: statechart :: state_machine < Machine, States:: Start > { } ;

И собственно сами состояния. Внутри состояний требуется определить тип описывающий переходы (reactions ), а если переходов несколько, то перечислить их в списке типов boost::mpl::list . Второй параметр шаблона simple_state – тип описывающий машину. Переходы описываются параметрами шаблона transition, парой Событие — Следующее состояние :

namespace States { struct Start : boost:: statechart :: simple_state < Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word > > reactions; } ; struct Number : boost:: statechart :: simple_state < Number, Machine> { typedef boost:: mpl :: list < boost:: statechart :: transition < Events:: Space , States:: Start > , boost:: statechart :: transition < Events:: Letter , States:: Skip > , boost:: statechart :: transition < Events:: Unknown , States:: Skip > > reactions; } ; struct Word : boost:: statechart :: simple_state < Word, Machine> { typedef boost:: mpl :: list < boost:: statechart :: transition < Events:: Space , States:: Start > , boost:: statechart :: transition < Events:: Digit , States:: Skip > , boost:: statechart :: transition < Events:: Unknown , States:: Skip > > reactions; } ; struct Skip : boost:: statechart :: simple_state < Skip, Machine> { typedef boost:: statechart :: transition < Events:: Space , States:: Start > reactions; } ; }

Машина построена, осталось только инициализировать ее и можно использовать:

Machine machine; machine.initiate () ; ... machine .process_event (Events:: Space () ) ;

Итог:

Гибкость, расширяемость

— Эффективность

Быстродействие

Я написал тестовую программу для проверки быстродействия построенных автоматов. Через автоматы я прогнал текст размером ~17 Мб. Вот результаты прогона:

Loading text Text length: 17605548 bytes 0.19 s Running BoostMachine Words: 998002, numbers: 6816 0.73 s Running DynamicMachine Words: 998002, numbers: 6816 0.56 s Running FastDynamicMachine Words: 998002, numbers: 6816 0.29 s Running SimpleMachine Words: 998002, numbers: 6816 0.20 s

Что осталось не рассмотренным

Неохваченными остались еще несколько реализаций конечных автоматов (рекомендую http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml и http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), генераторы строящие автоматы из описаний, библиотека Meta State Machine из Boost версии 1.44.0, а также формальные описания конечных автоматов. Со всем перечисленным любопытный читатель может ознакомиться самостоятельно.

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

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

· конечный автомат может решать ряд легких задач компиляции. Лексический блок почти всегда строится на основе конечного автомата.

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

· моделирование конечного автомата требует фиксированного объема памяти, что упрощает управление памятью.

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

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

Определение: Конечный автомат - это формальная система, которая задается с помощью следующих объектов :

· конечным множеством входных символов;

· конечным множеством состояний;

· функцией переходов, которая каждой паре (текущее состояние, входной символ) ставит в соответствие новое состояние;

· начальным состоянием;

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

Пример. Разберем работу контроллера, проверяющего четно или нечетно число единиц в произвольной цепочке, состоящей из нулей и единиц. Допустим, что соответствующий конечный автомат должен « допускать» все цепочки, содержащие нечетное число единиц и « отвергать » цепочки с четным их числом. Назовем этот автомат « контроллером четности ». Считаем, что символы, отличные от 0 и 1 нельзя подавать на вход автомата. Итак, входной алфавит контроллера есть множество {0, 1} . Считаем, что в конкретный момент времени конечный автомат имеет дело лишь с одним входным символом, а информацию о предыдущих символах входной цепочки сохраняет с помощью конечного множества состояний. В качестве множества состояний будем рассматривать множество { чет, нечет }, одно из этих состояний должно быть выбрано в качестве начального. Пусть им будет состояние {чет}, поскольку на первом шаге число прочитанных единиц равно нулю, а нуль есть четное число. При чтении очередного входного символа состояние автомата либо меняется, либо сохраняется прежним причем новое его состояние зависит от входного символа и текущего состояния. Такое изменение состояния называется переходом.

Работа автомата может описываться математически функцией переходов вида d(Sтек., x) = Sнов. Иначе это можно записать следующим образом:

d (чет., 0) = чет. d (чет., 1) = нечет.

d (нечет., 0) = нечет. d (нечет., 1) = чет.

Контроллер имеет единственное допускающее состояние НЕЧЕТ, а ЧЕТ есть « отвергающее » состояние. Отразим последовательность переходов автомата при подаче на его вход цепочки 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблица переходов такого автомата имеет вид: