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

Сколько стоит твоя работа?
Тип работы:*
Тема:*
Телефон:
Электронная почта:*
Телефон и почта ТОЛЬКО для обратной связи и нигде не сохраняется.

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

Эквивалентные автоматы

Автоматы являются устройствами для переработки дискретной информации. При этом характером перерабатываемой информации определяется входной и выходной алфавиты (X и Y); алфавит внутренних состояний (Q) определяется строением автомата и, вообще говоря, он может различаться у разных автоматов с одинаковыми входными и выходными алфавитами. Следовательно, одно и то же преобразование информации может быть осуществлено автоматами с разным числом состояний и, следовательно, посредством различного числа команд. Введем ряд определений:

Состояния q автомата М и q' автомата М' считаются эквивалентными,если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают ее в одинаковую выходную последовательность.

Автоматы М и М' называются эквивалентными,если для каждого состояния автомата М существует эквивалентное ему состояние автомата М' и наоборот.

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

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

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

Автомат, эквивалентный заданному и имеющий наименьшее из всех возможных число состояний называется минимальным.

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

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

 

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

Пример 2.1

Пример 10.1

Представление элементарных данных в ОЗУ

Классификация данных. Проблемы представления данных

Пример 5.4

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

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

 
 

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