TVPS_posobie_13_06_2013

Реакция автомата из примера 61 на диагностирующие слова

	00	01	10	11
q*	00	00	00	01
1
q*	01	00	10	10
2
q*	10	10	00	01
3

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

3.8.Задача минимизации КА

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

Введем понятие эквивалентных состояний автоматов и эквивалентных автоматов.

Определение. Состояние q автомата M и q' автомата M' будем называть эквивалентными состояниями, если оба автомата,

получив одну и ту же произвольную последовательность в состояниях q и q' соответственно, перерабатывают ее в одинаковую выходную последовательность.

Определение. Автоматы M и эквивалентными автоматами, если автомата M существует эквивалентное наоборот.

M'	будем	называть
для	каждого	состояния

состояние автомата M' и

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

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

161

Шаг 1. Нахождение эквивалентных состояний

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

Таблица 23

Исходный КА

a	q	q1	q2	q3		q4	q5	q6
0		q4, 1	q2, 0	q4, 1		q4, 1	q6, 0	q5, 0
1		q6, 0	q2, 0	q2, 0		q3, 0	q6, 0	q6, 0
2		q1, 0	q6, 1	q3, 0		q3, 0	q5, 1	q2, 1

Составим треугольную таблицу, клетки которой соответствуют всем различным неупорядоченным парам состояний qiqj (i j), и заполним еѐ так: если для состояний qi и qj существует входной символ х, приводящий к разным значениям выхода, то соответствующую клетку таблицы перечеркнем крестом.

В нашем примере перечеркивается, в частности, клетка, соответствующая паре q1q2, так как при x=0 автомат в состояниях q1 и q2 выдает 1 и 0 соответственно.

Если же при каждом х выход автомата в состояниях qi и qj принимает одинаковые значения, то в клетке записываются все пары состояний qvqw (v w), отличные от qiqj, в которые автомат может перейти из qi и qj, при подаче одного и того же входного символа. Так, например, в клетке q5q6 следует записать пару q2q5, возникающую при x=2, так как х=0 приводит к исходной паре q5q6, a x=1 приводит к паре q6q6 одинаковых состояний.

Рассматриваемому примеру соответствует треугольная таблица

(Рис. 99).

162

q2
q3	q2 q6
q4	q3 q6			q2 q3
	q1 q3
q5		q2	q6
		q5	q6
q6		q2	q5			q2 q5
	q1	q2		q3	q4	q5

Рис. 99. Нахождение эквивалентных состояний, итерация 1

Далее зачеркнем в таблице клетки, в которых присутствуют пары, соответствующие уже вычеркнутым клеткам. В данном случае следует зачеркнуть клетку для пары q3q4 (так как в ней содержится q2q3) и клетку для пары q1q4 (в ней содержится q3q6). После этого таблица приобретает следующий вид (Рис. 100).

q2
q3	q2 q6
q4
q5		q2	q6
		q5	q6
q6		q2	q5			q2 q5
	q1	q2		q3	q4	q5

Рис. 100. Нахождение эквивалентных состояний, итерация 2

Затем снова зачеркнем все клетки, которые содержат пары, соответствующие вычеркнутым клеткам и т.д., пока не образуется таблица, в которой ни одной клетки вычеркнуть нельзя. В данном примере этим свойством обладает таблица, представленная на Рис. 100.

163

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

Действительно, если состояния q' и q" неэквивалентны, то найдется входная последовательность х=x1x2...xp, на которой автомат, запущенный в состояниях q' и q", выдает разные входные последовательности.

На основе таблицы из Рис. 100 выпишем все эквивалентные пары: q1q3, q2q5, q2q6 и q5q6. Класс эквивалентности образуется состояниями, которые попарно эквивалентны. В данном случае получаем классы {q1, q3} и {q2, q5, q6}. Каждое состояние, не вошедшее ни в один из этих классов, эквивалентно лишь себе и само образует класс эквивалентности. Добавив эти классы, получаем требуемое разбиение. В рассматриваемом примере к классам {q1, q3} и {q2, q5, q6} необходимо добавить класс {q4}.

Шаг 2. Построение минимального автомата

Определение. Пусть имеется некоторое разбиение всех состояний автомата M на множества Q1, Q2, ..., Qs. Разбиение назовем замкнутым, если для любого множества Qv и любого входного сигнала х множество всех состояний, в которые под действием х переходят состояния из Qv, целиком содержится в некотором множестве Qw, зависящем от v и х.

Разбиение множества состояний на классы эквивалентности является замкнутым. Действительно, если состояния qi и qj эквивалентны и при подаче х они переходят в состояния qi' и qj', то последние также эквивалентны. Если бы это было не так и существовала входная последовательность xi, ..., xp, дающая в применении к состояниям qi' и qj' разные выходные последовательности, то последовательность xi, ..., xp, примененная к qi и qj также приводила бы к разным выходным последовательностям, что противоречит эквивалентности qi и qj. Таким образом, состояния из одного класса эквивалентности при подаче одинакового входного воздействия снова попадают в один класс эквивалентности, что и указывает на замкнутость разбиения.

164

Имея разбиение множества состояний Q автомата М на классы эквивалентности Q1, Q2,..., Qs, построим новый автомат M'. Для этого каждому классу Qv сопоставим состояние qv' (v=1, 2, ..., s), а в качестве входного и выходного алфавитов автомата М' возьмем соответствующие алфавиты автомата M.

Чтобы назначить переход в автомате М из состояния qv' под действием х, рассмотрим соответствующий класс эквивалентности Qv. Согласно свойству замкнутости входной сигнал переводит все состояния из Qv в некоторый класс эквивалентности Qw. Им определяется следующее состояние qw'.

По свойству эквивалентности состояний подача входного воздействия х в каждом состоянии из Qv приводит к одинаковому значению выхода. Оно принимается в качестве выходного значения, соответствующего переходу в автомате М' из qv' под действием х.

Сопоставим классам эквивалентности Q1={q1, q3}, Q2={q2, q5, q6}, Q3={q4} состояния q1', q2' и q3' соответственно и получим новый КА (табл. 24).

Таблица 24

КА после минимизации

x	q	q1'	q2'	q3'

0 q3', 1 q2', 0 q3', 1

1q2', 0 q2', 0 q1', 0

2q1', 0 q2', 1 q1', 0

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

165

3.9.Языки конечных автоматов

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

Машины. Языки и грамматики

Рассмотрим грамматику

(N, T, P, S),

где N – алфавит нетерминальных символов, T – алфавит терминальных символов,

P – конечное множество продукций (или правил подстановки),

S – начальный символ.
	Продукция имеет вид α	,	где α N*,	(N T)*. Продукция
α	может быть применена	к	некоторому	слову вида	1α 2 и
преобразует его в слово 1 2.
	Последовательность слов	0,	1, …, n, такая что слово		i получено

из слова i-1, 1≤i≤n, с помощью некоторой продукции из P, называется выводом в данной грамматике.

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

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

Определение. Грамматика порождает контекстно-зависимый язык, если каждая продукция в P имеет вид

α1Dα2 α1 α2,

где D N, α1, α2 (N T)*, (N T)*. 166

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

D ,

где D N, (N T)*.

Класс контекстно-свободных (КС) языков является собственным подклассом класса контекстно-зависимых языков.

Определение. Если каждая продукция в P имеет вид

D D' или D	D',
где D – пустой символ или D N,	(N T)*, то грамматика
порождает регулярный язык.

Класс регулярных языков является собственным подклассом класса КС-языков.

Регулярные языки порождаются КА и поэтому называются также автоматными языками.

Язык конечного автомата

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

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

Определение. Множество всех слов, принимаемых автоматом, образует язык КА.

Замечание. Конечное состояние помечается одним из специальных символов (Рис. 101), заключительных вершин может быть несколько.

167

#

Рис. 101. Пометки для заключительных вершин КА

Пример 62. Дан КА (рис. 102). Определить язык КА.

*

q0

a

q1

a

b

b

q3

a

q2

b

b

Рис. 102. КА для примера 62

Язык КА La={anbm | n, m

N }.

Определение. Регулярной грамматикой назовем четверку

G=(N, T, P, S),

где N – алфавит нетерминальных символов, T – алфавит терминальных символов,

P – конечное множество продукций (или правил подстановки), S – начальный символ.

Продукция имеет вид:

D αB,

D α,

где D, B N, α T.

(*)

(**)

Пример 63. Пусть грамматика G имеет продукции следующего вида: S aS|aB, B bB|b. Тогда язык L(G)={anbm}.

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

168

множества N, кроме конечной вершины, которая помечается символом «#». Вершина, соответствующая начальному символу S помечается специальным значком «*». Для продукций вида (*) в графе строится дуга из вершины D в вершину B, дуга помечается символом «α». Для продукций вида (**) строится дуга из вершины D в заключительную с пометкой «α». Каждая дуга в графе соответствует одной и только одной продукции в грамматике.

Пример 64. Пусть грамматика G имеет продукции следующего вида: S aD|bB, D aD|a, B bB|b. Построить для нее граф

(Рис. 103).

* S	a	D	a
b			a
B	b	#
	b

Рис. 103. Граф для примера 64

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

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

В данном примере имеем недетерминированный автомат, так как вершины D и B имеют по две исходящих дуги с одинаковыми пометками.

169

Определение. Детерминированным КА будем называть пятерку

M=(A, Q, q0, , F),

где A – входной алфавит,

Q – внутренний алфавит, q0 – начальное состояние,

– функция переходов,

F – множество заключительных состояний.

Определение. Пусть : Q A* Q – расширенная функция переходов:

(q, α)= ( (q, a), ), где α=а , α A*, а A, A*.

Тогда множество строк, принимаемых КА, имеет вид:

C(M)={α A*| (q, α) F}.

Другими словами, слово α – это такая строка, что автомат попадает в одно из конечных состояний.

Определение. Два КА эквивалентны, если они имеют одинаковые языки.

Сравнение языков сетей Петри и конечных автоматов

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

Множество всех слов, допускаемых автоматом, образует его

язык. На Рис. 104 показан пример конечного автомата, допускающего язык {anbm| n>0, m>0}.

170