Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации

Загрузка...

Пример 9.5

Пусть имеется конечный автомат, заданный таблицей:

На основе ее составим другую таблицу, клетки которой будут соответствовать всем различным парам qiqj (ij), заполнив ее согласно следующим правилам:

· если два состояния qi и qj неэквивалентны (т.е. для какого-либо значения входного символа х значения на выходе различаются), то соответствующая клетка зачеркивается;

· если в состояниях qi и qj для каждого х значения на выходе одинаковы, то в клетки записываются все пары состояний qvqw (vw), отличные от qiqj, в которые автомат может перейти из qi и qj при подаче одного и того же входного символа.

Согласно первому правилу зачеркнутой оказалась, например, клетка, соответствующая паре q1q2, поскольку при х = 0 на выходе выдаются разные значения (1 и 0). По второму правилу, например для пары q5q6 следует записать пару q2q5 из следующих соображений: у q5 и q6 все выходные символы одинаковы при одинаковых входных; х = 0 приводит к исходной паре q5q6; х = 1 приводит к паре одинаковых состояний q6q6.

Подобным образом анализируются остальные сочетания.

Наконец, последующими преобразованиями вычеркиваются клетки, в которых находятся пары, соответствующие уже зачеркнутым ранее клеткам. Например, следует зачеркнуть клетку для пары q1q4, поскольку в ней содержится q3q6, а также q3q4, так как в ней есть q2q3. Затем снова нужно зачеркнуть все клетки, которые содержат пары, соответствующие вычеркнутым клеткам. Процедура должна продолжаться до тех пор, пока не сформируется таблица, в которой нельзя вычеркнуть ни одной из оставшихся клеток. Для рассматриваемого примера эти клетки выделены жирной рамкой. Можно доказать, что оставшиеся не вычеркнутыми клетки соответствуют всем парам эквивалентных состояний. Это q1q3, q2q5, q2q6 и q5q6. Классы эквивалентности образуются состояниями, которые попарно эквивалентны. В этом случае это {q1,q3} и {q2, q5, q6}. Состояния, не вошедшие в эти классы, эквивалентны лишь себе и образуют собственные классы эквивалентности; в рассматриваемом примере это {q4}. Таким образом, классы эквивалентности оказались выделенными.

После выделения классов эквивалентности состояний для автомата М можно построить эквивалентный ему автомат M'. В качестве входного и выходного алфавитов для М' возьмем соответствующие алфавиты М, а каждому классу эквивалентных состояний М сопоставим одно состояние М'. Для рассмотренного выше примера можно принять (q1)' ↔ {q1, q3}, (q2)' ↔ {q2, q5, q6}, (q3)' ↔ {q4}.

Окончательно получаем таблицу нового автомата М'.

Можно доказать следующую теорему*:

* Интересующихся доказательством можно адресовать к книге Л.А. Шоломова [48, с.125-126].





 

Читайте также:

Начальные определения

Пример 4.1

Энтропия опыта равна той информации, которую получаем в результате его осуществления.

Любому неструктурному алгоритму может быть построен эквивалентный ему структурный алгоритм.

Пример 7.9

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1662

 
 

54.225.20.19 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.