Алфавит, слова, операции над словами (стр. 2 )

Т. о., сопоставляя доказанные утверждения, получаем:

Класс А-языков и класс языков, распознаваемых конечными автоматами, совпадает.

Так, например, для автомата, представленного на рис. 5, соответствующий детерминированный автомат представлен на рис. 6.

Рис.6

Здесь F(S, a)= [S, A] = A’

F([S, A], a) = [S, A]

F([S, A],b) = [A, K] = K’

F([A, K],b)= [A, K] = K’

Для автомата на рис. 7а детерминированный автомат представлен на рис.7b.

Рис.7

Алгоритм построения детерминированного автомата по недетерминированному:

Строим начальное состояние q0’= [q0], помечаем его как начальное.

Для каждого состояния, построенного на предыдущем шаге, строим

F(qi’, a) для всех aÎVT. Если для какого-нибудь из построенных состояний функция перехода ещё не построена, возвращаемся к шагу 2.

Помечаем как конечные все состояния qi’= / Ç K¹Æ.

Конечность процесса обеспечивается конечностью множества P(Q).

Автоматы с l - переходами.

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

Рис. 8

Рис.9

Например, рассмотрим автомат с двумя выходами, представленный на рис. 9. Он имеет два выхода. Если просто объединить две выходные вершины, то получившийся автомат не будет эквивалентен исходному, т. к. после построения символа b в результирующем автомате возможно будет построение символов а, что было невозможно в исходном автомате. Эквивалентный исходному автомат представлен на рис. 10.

Рис.10.

Иногда в двухполюснике конечные состояния изображаются как

Очевидно, что если L – А-язык, то ему можно сопоставить двухполюсник.

Пусть языкам L1 и L2 сопоставлены соответствующие двухполюсники

(рис.11 а). Тогда их объединению, конкатенации и итерации языка L1 будут, соответственно, сопоставлены двухполюсники рис. 11б, 11в, 11г

Рис.11

Т. о. доказана теорема: Класс А-языков замкнут относительно операций объединения, конкатенации и итерации.

Оптимизация автоматов с l-переходами.

Если из состояния А исходит единственная дуга и это l-дуга в состояние В, то вершины А и В можно слить.

Если из вершины А выходит l-дуга в вершину В, являющуюся начальной вершиной некоторой дуги( не петли) или последовательности дуг, а С – конечная вершина этой дуги (последовательности дуг), и единственная дуга из С - l-дуга в вершину А, то вершины А, В и С можно слить (примеры такого слияния приводятся на рис. 12 ( для одной дуги – а, б; для последовательности – в, г).

Рис.12

Теорема:

Классы языков, допускаемых детерминированными автоматами и автоматами с l-переходами, совпадают.

Док-во:

Пусть автомат А = <Q, VT, q0, F, K> - автомат l-переходами. Построим соответствующий детерминированный автомат А’= <Q’, VT, q0’, F’, K’>, такой, что L(A)=L(A’) следующим образом.

F’(q, a)={p / (q, ax) ├+ (p, x)}

K’ = K È{p / (q, l) ├* ( p, l)& pÎK}

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

Пример. Пусть автомат представлен диаграммой на рис. 13а. Объединим по правилу 1 упрощения автоматов с l-переходами состояния 4 и 5 и переобозначим состояния, как показано на рис. 13б.

Построим функцию переходов детерминированного автомата А’.

F(A, a) = [B, C, D, F] F(A, b) = [E] F(A, c) = Æ	F([B, C, D, F], a) = [C, D, F], F([B, C, D, F], b) = [D, E], F([B, C, D, F], c) = Æ,	F([E], a) = Æ, F([E], b) = Æ, F([E], c) = [D],
F([C, D, F], a) = [C, D, F] F([C, D, F], b) = [E] F([C, D, F],c) = Æ	F([D, E], a) = [D, F] F([D, E], b) = [E] F([D, E],c) = [D]	F([D, F], a) = [D, F] F([D, F], b) = [E] F([D, F], c) = Æ
F([D], a) = [D, F] F([D], b) = [E] F([D], c) = Æ

K’ = { [B, C, D, F] , [ D, F], [C, D, F]}

Диаграмма детерминированного автомата представлена на рис. 14.

Рис.14

Тот же автомат после переобозначения состояний представлен на рис. 15.

Рис.15

9. Минимизация числа состояний автомата

9.1. Лингвистический автомат.

Алгоритм на основании языка L, порождаемого автоматом.

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

Строятся матрицы D0, D1,… указывающие различимость состояний по строкам длины n. Состояния qi и qj различимы по строке длины 0( 1 на пересечении строки i и столбца j матрицы D0): qi D0 qj Û (qiÎK ) & ( qjÏ K) Ú (qiÏ K)&( qjÎK).

Далее определение по индукции: при i > 0 состояния qk и qj различимы по строке длины i, т. е. (qk Di qj )Û qk Di-1 qj или $aÎVT, такой, что F(qk, a) Di-1 F(qj, a).

Состояние qk различимо от состояния qj, если $ i³ 0 , такое, что qk Di qj.

Очевидно, что qk Di qj Û существует строка Х, ½Х½£ i, что (F(qi, X)ÎK ) & ( F(qj, X)Ï K) Ú (F(qi, X)Ï K)&( F(qj, , X)ÎK).

Пример.

Диаграмма автомата представлена на рис. 16.

Рис.16

Матрицы, получающиеся при анализе автомата:

D0

F T F T T F T T F T

D1

F T F T T T T T F T

D1=D2

Из анализа полученной матрицы получаем три класса эквивалентных состояний:

K1 = {1, 4}, K2 = {2}, K3 = {3,5}. Диаграмма полученного автомата представлена на рис. 17.

Рис.17

9.2. Метод Хафмена.

Этот метод работает как для лингвистических автоматов, так и для автоматов Мили.

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

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

Например, рассмотрим автомат, диаграмма которого представлена на рис. 18

Рис.18

1. Составляем таблицы переходов и выходов.

	A	B	C	D	E	F	G
0	B	1	D	1	E	0	D	1	A	0	G	0	D	0
1	F	0	C	0	G	1	C	0	F	1	E	1	C	1

2. Составляем классы предположительно эквивалентных состояний (т. е. состояний, при переходе из которых на одинаковые входы выдаются одинаковые выходы).

В данном случае это классы K1= {A, B, D}, K2= {C, E, F, G}

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

	A	B	C	D	E	F	G
0	K1	K1	K2	K1	K1	K2	K1
1	K2	K2	K2	K2	K2	K2	K2

Если в пределах одного класса состояния ведут себя по-разному, то класс разбивается на соответствующие подклассы, и возвращаемся к шагу 3.

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

4. Если во всех классах состояния ведут себя одинаково, то это действительно классы эквивалентности.

Строится автомат, состояниями которого являются классы эквивалентности исходного автомата.

В нашем примере класс К2 разбивается на 2 класса - К3= {C, F}, К4 = {E, G}

	A	B	C	D	E	F	G
0	K1	K1	К4	K1	К4	К4	К4
1	К3	К3	К4	К3	К3	К4	К3

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

Рис.19

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

Применение метода к автомату, диаграмма которого представлена на рис. 16, имеющему таблицу переходов

	1	2	3	4	5
a	2	2	1	2	4
b	3	4	2	5	2

и конечные состояния 3, 5, на первом шаге дает классы К1 = {3, 5}, K2= {1, 2, 4} и, соответственно, получаем таблицу переходов:

	1	2	3	4	5
a	K2	K2	K2	K2	K2
b	К1	K2	K2	К1	K2

Видно, что класс K2 разбивается на два класса K3= {1, 4}, K4={2}. Получается таблица переходов

	1	2	3	4	5
a	K4	K4	K3	K4	K3
b	К1	K3	K4	К1	K4

Очевидно, что, как и следовало ожидать, получившийся минимальный автомат совпадает с тем, который получен в пункте 9.1. Диаграмма полученного автомата приведена на рис. 17.