Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

5.5. Минимизация конечных автоматов кратко

Лекция



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

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

Минимизация числа состояний полных автоматов связана с отношением эквивалентности. Пусть автоматы А1 и А2, (эти обозначения могут относиться к одному и тому же автомату) под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т.е автоматы А1 и А2 в данных состояниях qi и qj неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Очевидна справедливость следующих положений:

1) состояния qi и qj автомата явно различимы, если различаются соответствующие им строки в таблице выходов;

2) состояния qi и qj автомата явно эквивалентны, если соответствующие им строки в таблице переходов и в таблице выходов одинаковы или становятся одинаковыми при замене каждого номера qi на qj (или наоборот).

Метод абстрактной минимизации автомата был предложен Хафменом. Он основан на склеивании эквивалентных состояний и состоит в последовательном выделении классов эквивалентных состояний с помощью таблиц выходов и переходов. Рассмотрим метод Хафмена на примере.

Пусть задан автомат, граф которого представлен на рис. 5.10а, а общая таблица переходов – табл. 5.12. Из этой таблицы следует, что состояния из множества {0, 3, 4} являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинако­выми при замене в числителе цифры 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0, 4} и {1, 5}.

5.5. Минимизация конечных автоматов

а) б)

Рис. 5.10

Таблица 5.12

xv

qv

0

1

2

0

1

2

3

4

5

6

1/1

5/1

1/0

3/1

1/1

1/0

5/0

4/0

1/1

1/1

2/0

4/0

5/1

5/1

4/1

4/1

6/1

0/1

4/1

4/1

2/1

Объединяя эквивалентные состояния в автомате А1, получаем эквивалентный автомат А2 с меньшим числом состояний, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы А1 и А2 являются эквивалентными, если каждому состоянию qi автомата А1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата А2 и если каждому состоянию qj автомата А2 соответствует хотя бы одно эквивалентное ему состояние автомата А1.

Таблица 5.13 Таблица 5.14

xv

qv

0

1

2

xv

qv

0

1

2

0(4)

1(5)

2

3

6

1/1

1/0

1/0

3/1

1/0

0/0

1/1

1/1

2/0

1/1

0/1

0/1

6/1

0/1

2/1

0(4)

1(5)

2(6)

3

1/1

1/0

1/0

3/1

0/0

1/1

1/1

2/0

0/1

0/1

2/1

0/1

Эквивалентные состояния, например, qi и qj, удобно объединять по общей таблице переходов, вычеркивая строку qj и заменяя везде в числителе числа qj на qi. Об этом говорит сайт https://intellect.icu . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состояний. Так, для рассматриваемого примера получаем последовательно табл. 5.13 и табл. 5.14. Таблица 5.13 соответствует объединению двух пар эквивалентных состояний {0,4} и {1, 5}, а табл. 5.14 – объединению одной пары {2, 6}. Полученный минимальный автомат содержит только четыре состояния (рис. 5.10б).

Если известны все пары эквивалентных состояний конечного автомата, то тогда на множестве Q его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является само это состояние. Обозначим через q'0 q'1q'v представители классов эквивалентности и через А' – автомат, множеством состояний которого является семейство представителей Q' = { q'0 q'1q'v }. Можно утверждать, что автоматы А и А' эквивалентны (А ~ А'), причем А' имеет минимальное число состояний, т. е. является минимальной формой автомата.

Объединение эквивалентных состояний в классы эквивалентности осуществляется весьма просто. Если qi ~ qj и qj ~ qk, то на основе свойства транзитивности следует, что qi ~ qk и, значит, пары { qi ~ qj} и { qj ~ qk} входят в общий для них класс эквивалентности. Но для выявления всех пар эквивалентных состояний требуется более громоздкая процедура, так как множество таких пар не исчерпывается явно эквивалентными состояниями и не всегда может быть полностью обнаружено и объединено изложенным выше способом.

Для эквивалентного разбиения множества Q состояний автомата предложен ряд способов. Один из них основан на последовательном рассмотрении всевозможных пар состояний и исключении тех из них, которые не являются эквивалентными. При этом пары одинаковых состояний { qi, qi }, являющиеся в силу свойства рефлективности заведомо эквивалентными (qi ~ qi), не рассматриваются. Процедура эквивалентного разбиения осуществляется по таблице пар состояний, которая получается на основе общей таблицы переходов автомата. Так как явно различимые пары состояний (для таких состояний строки в таблице выходов различные) не могут быть эквивалентными, то в таблицу пар они не включаются. Для каждой пары отводится строка, для каждого входа – столбец, а в клетках на основании таблицы переходов указывается пара состояний, в которые переходит автомат из данной пары состояний при данном входном воздействии (порядок записи состояний в каждой паре безразличен). Исключаемые пары отмечаются каким-либо способом (набираются жирным шрифтом, подчеркиваются или снабжаются меткой). Общая таблица переходов и полученная из нее таблица пар состояний некоторого автомата представлены соответственно как табл. 5.15 и табл. 5.16.

Таблица 5.15 Таблица 5.16

xv

qv

0

1

2

xv

Пары

0

1

2

0

1

2

3

4

5

6

7

8

1/1

0/0

1/1

2/0

5/1

7/0

5/1

3/1

6/0

1/0

3/1

1/0

1/1

3/0

8/1

1/0

3/0

8/1

4/0

3/1

4/0

1/1

2/0

5/1

7/0

6/0

6/1

0,2

√0,4

√0,6

0,7

1,3

√1,5

√1,8

√2,4

√2,6

2,7

√3,5

√3,8

4,6

√4,7

√5,8

√6,7

1,1

1,5

1,5

1,3

0,2

0,7

0,6

1,5

1,5

1,3

2,7

2,6

5,5

3,5

6,7

3,5

1,1

1,3

1,1

1,3

1,3

3,8

3,8

1,3

1,1

1,3

1,8

1,8

1,8

3,3

8,8

1,3

4,4

2,4

4,7

4,6

1,3

3,5

3,6

2,4

4,7

4,6

1,5

1,6

2,7

2,6

5,6

6,7

Так как одинаковые строки таблицы выходов соответствуют множествам состояний {0, 2, 4, 6, 7} и {1, 3, 5, 8}, то в первом столбце таблицы пар указаны только попарные комбинации таких состояний, которые входят в одно и то же множество, т.е. не являются явно различимыми.

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

В приведенном примере на первом шаге отмечаются пары (1, 8}, (3, 8} и {5, 8}, на втором – {1,5} и {3, 5}, на третьем – {0, 4}, {0, 6}, {2, 4), {2, 6}, {4,7} и {6, 7}. Эквивалентными являются неотмеченные пары {0,2}, {0,7}, {1,3}, {2,7} и (4,6), образующие классы эквивалентности Q0 = (0, 2, 7}, Q1 = {1, 3} и Q2 = {4, 6). Кроме того, не вошедшие в эти множества состояния 5 и 8 образуют классы эквивалентности Q3 = {5} и Q4 = {8}. Обозначив представителей полученных пяти классов соответственно числами от 0 до 4, получим для рассматриваемого автомата минимальную форму с пятью состояниями и общей таблицей переходов (табл. 5.17).

Таблица 5.17 Таблица 5.18

xv

qv

0

1

2

xv

qv

0

1

0

1

2

3

4

1/1

0/0

3/1

0/0

2/0

1/0

1/1

1/0

4/1

4/1

2/0

1/1

0/0

3/1

2/1

0

1

2

3

4

5

1/0

3/0

5/–

5/0

4/1

1/0

5/0

5/–

Следует отметить, что автомат, все состояния которого эквивалентны, сводится к автомату с одним состоянием, т. е. представляет собой по существу комбинационную схему. Автомат, среди состояний которого нет эквивалентных, является несократимым. Если А' – минимальная форма автомата А, то она единственна и несократима.

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

создано: 2018-05-21
обновлено: 2021-03-13
132267



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

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

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