Конспект лекций Киров 2010 удк 681. 332




НазваниеКонспект лекций Киров 2010 удк 681. 332
страница10/17
Дата публикации21.08.2013
Размер0.75 Mb.
ТипКонспект
zadocs.ru > Химия > Конспект
1   ...   6   7   8   9   10   11   12   13   ...   17
^

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


Рассмотрим метод, предположенный Ауфенкампом и Хоном.

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

Два состояния абстрактного автомата xm и xs называются эквивалентными, если выходная функция для всех возможных входных слов Ф. Иначе состояния называются неразличимыми.

Более слабой формой эквивалентности является k-эквивалентность:

для всех возможных слов длиной k.

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

Рассмотрим алгоритм минимизации числа внутренних состояний полностью определённого автомата:

  1. Находятся последовательные разбиения , множества X до тех пор, пока на каком-то (k+1) шаге не окажется, что это разбиение ничем не отличается от предыдущего. Доказано, что в этом случае (=) есть необходимое нам разбиение, и дальнейшее сокращение числа внутренних состояний автомата невозможно.

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





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

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

ПРИМЕР:

Минимизация полного автомата Мили:

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




X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

1

X10

X12

X5

X7

X3

X7

X3

X10

X7

X1

X5

X2

2

X5

X8

X6

X11

X9

X11

X6

X4

X6

X8

X9

X8


Таблица выходов:




X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

1

1

1

2

2

1

2

1

1

2

2

2

2

2

2

2

1

1

2

1

2

2

1

1

1

1

={X1,X2,X5,X7,X8} B1,

{X3,X4,X6,X9,X10,X11,X12 } B2





X1

X2

X5

X7

X8




X3

X4

X6

X9

X10

X11

X12

1

B2

B2

B2

B2

B2




B1

B1

B1

B1

B1

B1

B1

2

B1

B1

B2

B2

B2




B2

B2

B2

B2

B1

B2

B1

={X1,X2} C1,

{X5,X7,X8} C2,

{X3,X4,X6,X9,X11} C3,

{X10,X12}C4,





X1

X2




X5

X7

X8




X3

X4

X6

X9

X11




X10

X12

1

C4

C4




C3

C3

C4




C2

C2

C2

C2

C2




C1

C1

2

C2

C2




C3

C3

C3




C3

C3

C3

C3

C3




C2

C2

={X1,X2} D1,

{X5,X7} D2

{X8} D3

{X3,X4,X6,X9,X11} D4

{X10,X12} D5
Соответственно, получили разбиение, для которого дальнейшее разбиение невозможно.

Произвольно выбираем из каждого класса по одному состоянию и формируем множество






X1

X3

X5

X8

X10

1

X10

X5

X3

X10

X1

2

X5

X3

X3

X3

X8






X1

X3

X5

X8

X10

1

1

2

1

1

2

2

2

1

2

2

1


Особенности минимизации для автомата Мура.




1

1

3

3

3

2

3

1

2

2

2

2




X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

1

X10

X12

X5

X7

X3

X7

X3

X10

X7

X1

X5

X2

2

X5

X7

X6

X11

X9

X11

X6

X4

X6

X8

X9

X8


При минимизации автомата Мура вводится понятие 0-эквивалентности и, соответственно, разбиения множества внутренних состояний на 0- эквивалентные классы. 0- эквивалентными называются любые одинаково отмеченные состояния автомата Мура. Если два 0- эквивалентных состояния любыми входными сигналами переводятся в два 0- эквивалентных состояния, то они называются 1-экивавлентными состояниями.

={X1,X2,X8} А1

{X3,X4,X5,X7} A2

{X6,X9,X10,X11,X12} А3

1   ...   6   7   8   9   10   11   12   13   ...   17

Похожие:

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине "инвестирование"
Конспект лекций по дисциплине «Инвестирование» для студентов экономических специальностей всех форм обучения Сост.: В. М. Гридасов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине “Каналообразующие устройства”, 2010 Перечень лекций
Тема №1 (4 часа) Назначение, основные параметры и состав каналообразующих устройств 5

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Витебск 2010 министерство образования республики...
Конспект предназначен для самостоятельного изучения, подготовки к практическим занятиям и экзамену по экономической теории

Конспект лекций Киров 2010 удк 681. 332 iconЭтика курс лекций (на основе книги: Этика (конспект лекций)
Этика (конспект лекций). – М.: «Приор-издат», 2002. Автор-составитель Аристотель. Никомахова этика. Сочинения: в 4-х т. Т. М.: Мысль,...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов направления 070104 «Морской и речной транспорт»
Конспект лекций рассмотрены и одобрены на заседании кафедры «Судовождение» кгмту

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по патологической анатомии инфекционных болезней. Киров, 2003
Вирусные инфекции представляют собой одну из многочисленных групп инфекционных заболеваний разнообразных по клиническому течению...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Утверждено Редакционно-издательским советом в качестве...
Чижов М. И., Юров А. Н. Информатика и информационные системы: Конспект лекций. Воронеж: Воронеж гос техн ун-т, 2003. 148 с

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине «Безопасность жизнедеятельности»
Безопасность в чрезвычайных ситуациях и гражданская оборона. Конспект лекций. Рубцов Б. Н. М. Миит, 2001

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций
Цифровые системы управления и обработки информации. Конспект лекций. Модуль 1: Организация и программирование систем чпу. (для студентов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов сектора второго высшего образования...
Конспект лекций разработан кандидатом экономических наук, доцентом кафедры «Экономическая теория и кибернетика» Одесского государственного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов