Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32



страница9/22
Дата07.11.2012
Размер1.2 Mb.
ТипКонспект
1   ...   5   6   7   8   9   10   11   12   ...   22

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

Минимизация автоматов методом таблиц различий


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

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

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

Различимость для строк ненулевой длины определяется по индукции: при i > 0 состояния qk и qj различимы по строке длины i, т.е. (qk Di qj ) qk Di-1 qj или aVT , такой, что F(qk,a) Di-1 F(qj,a).

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

Очевидно, что qk Di qj  существует строка x, x i , что (F(qk, x)K ) & ( F(qj, x) K) (F(qk, x) K) & (F(qj, , x)K).

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

Пример. Рассмотрим автомат SC, диаграмма которого представлена на рис. 14.



Рис.
14

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



D0

F T F T

T F T

T F

T


D1

T T F T

T T T

T F

T


D2=D1


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



Рис.15

K1 = {1, 4}, K2 = {2}, K3 = {3,5}. Диаграмма автомата, получающегося при объединении эквивалентных состояний автомата SC, представлена на рис. 15.

Минимизация автоматов по методу Хафмена


Этот метод применим как для лингвистических автоматов, так и для автоматов Мили (для них метод описан в разделе 12).

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

Алгоритм минимизации лингвистического автомата методом Хафмена.

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

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

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

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

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

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





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} и, соответственно, получаем таблицу переходов (для наглядности в таблицу добавлена строка, с указанием номера класса, которому принадлежит состояние):

№ класса

2

2

1

2

1

Вход\состояние

1

2

3

4

5

a

K2

K2

K2

K2

K2

b

К1

K2

K2

К1

K2

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

№ класса

3

4

1

3

1

Вход\состояние

1

2

3

4

5

a

K4

K4

K3

K4

K3

b

К1

K3

K4

К1

K4

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

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

Минимизация не полностью определенных автоматов


(на примере лингвистического автомата, диаграмма которого представлена на рис. 13).

При минимизации не полностью определенных лингвистических автоматов начальное разбиение множества состояний делается так же, как для полностью определённого автомата: на конечные и неконечные состояния. Для данного случая классы K1={B, C, F} – конечные состояния, K2= {A, D, E, G} – неконечные. Приведем таблицы переходов состояний для этого автомата.

Исходная таблица:





A

B

C

D

E

F

G

a

C

B

B

F

-

F

F

b

E

E

G

E

-

E

E

c

-

-

-

-

D

-

D


Проставляем классы состояний (в дополнительной верхней строке указываем номер класса состояния):





2

1

1

2

2

1

2




A

B

C

D

E

F

G

a

K1

K1

K1

K1

-

K1

K1

b

K2

K2

K2

K2

-

K2

K2

c

-

-

-

-

K2

-

K2


Далее разбиваем классы на подклассы в соответствии с одинаковостью и различием столбцов. Класс K2 разбивается на 3 класса K3 = {A, D}, K4 = {E}, K5 = {G}.




3

1

1

3

4

1

5




A

B

C

D

E

F

G

a

K1

K1

K1

K1

-

K1

K1

b

K4

K4

K5

K4

-

K4

K4

c

-

-

-

-

K3

-

K3


Получившаяся таблица показывает, что класс K1 также разбивается на два класса K6= {B, F}, K7 = {C}.




3

6

7

3

4

6

5




A

B

C

D

E

F

G

a

K7

K6

K6

K6

-

K6

K6

b

K4

K4

K5

K4

-

K4

K4

c

-

-

-

-

K3

-

K3


И, наконец, разбивается класс K3 : K8= {A}, K9={D}.




8

6

7

9

4

6

5




A

B

C

D

E

F

G

a

K7

K6

K6

K6

-

K6

K6

b

K4

K4

K5

K4

-

K4

K4

c

-

-

-

-

K9

-

K9


Это разбиение не приводит в дальнейшему разбиению классов и получившиеся классы состояний автомата являются классами эквивалентности, а автомат, состояниями которого являются классы эквивалентности исходного автомата, – минимальный. Диаграмма минимизированного автомата SB, на которой все классы, кроме 6-го, поименованы единственным входящим в них состоянием, а класс K6 – символом B, представлена на рис. 16.



Рис.16
1   ...   5   6   7   8   9   10   11   12   ...   22

Похожие:

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconМетодические указания к практическим занятиям Рязань 2004 удк 519. 713 (075)
Теория автоматов в задачах. Ч1: Методические указания к практическим занятиям/ Рязан гос радиотехн акад. Сост.: Н. И. Иопа. Рязань,...
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций москва 2003 ббк вкб / 075 : 378 я 14
История экономики России XX века (1900 – 1917 гг.) : Конспект лекций. – М.: Мгту "Станкин", 2003. – 45 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73 а 65 Рецензент И. П. Арешев
Охватывает ток (рис. 16), то
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций м осква 2000 ббк ВКП / 075 : 378 я 14
История экономики России XIX века: Конспект лекций. М.: Мгту "Станкин", 2000. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций по философии Часть 1 Античная философия Новосибирск 2007 удк 101. 8 (075) ббк ю3я73-1
Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций Таганрог 2001 удк 621. 382. 019. 3 (075. 8) Механцев Е. Б
Обеспечение надежности электронных средств: конспект лекций. Таганрог: Изд-во трту, 2001
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКурс лекций Для студентов вузов Кемерово 2006 удк 113/119(075) ббк 87я7 М42 Рецензенты

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org