Алгоритм минимизации заключается в следующем icon

Алгоритм минимизации заключается в следующем



НазваниеАлгоритм минимизации заключается в следующем
Дата конвертации16.11.2013
Размер32.64 Kb.
ТипЛекция
источник
1. /лекции по теории автоматов/Лекция 10ТА.doc
2. /лекции по теории автоматов/Лекция 11ТА.doc
3. /лекции по теории автоматов/Лекция 12 ТА.doc
4. /лекции по теории автоматов/Лекция 13 ТА.doc
5. /лекции по теории автоматов/Лекция 14 Т.doc
6. /лекции по теории автоматов/Лекция 15ТА.doc
7. /лекции по теории автоматов/Лекция 16 ТА.doc
8. /лекции по теории автоматов/Лекция 17ТА.doc
9. /лекции по теории автоматов/Лекция 1ТА.doc
10. /лекции по теории автоматов/Лекция 2ТА.doc
11. /лекции по теории автоматов/Лекция 3ТА.doc
12. /лекции по теории автоматов/Лекция 4ТА.doc
13. /лекции по теории автоматов/Лекция 5ТА.doc
14. /лекции по теории автоматов/Лекция 6 ТА.doc
15. /лекции по теории автоматов/Лекция 7ТА.doc
16. /лекции по теории автоматов/Лекция 8 ТА.doc
17. /лекции по теории автоматов/Лекция 9ТА.doc
Алгоритм минимизации заключается в следующем
Лекция 11 Элементарные автоматы
Лекция 12 d-триггер(триггер задержки)
Лекция 13 j-k триггер (универсальный триггер)
Лекция 14 Структурная схема конечного автомата
Лекция 15 Табличный метод структурного синтеза конечных автоматов
Лекция 16 Технические особенности конечных автоматов
Лекция 17 Вторая техническая особенность конечного автомата связана с возможностью возникновения неустойчивых состояний и так называемых «гонок»
Лекция 1 Синтез конечных автоматов
Лекция 2 Способы задания автомата
Лекция 3 Частичные автоматы
Лекция 4 Абстрактный синтез конечных автоматов
Лекция 5 Операции в алгебре событий
Лекция 6 Система основных событий
Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений. Абстрактный синтез обычно выполняется в два этапа
Сформулируем теперь общие правила подчинения мест регулярного выражения
После построения таблицы проведем второй этап минимизации числа внутренних состояний автомата. Можно объединить состояния, отмеченные индексами: 0 и 1v3, 4 и 3v6, 5 и 3v8

Лекция 10

Алгоритм минимизации заключается в следующем:

  1. Все внутренние разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y1 и y1 и следовательно будет две группы, которые мы обозначим буквами a и b.

  2. По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0.

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




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

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

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

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


Структурный синтез конечных автоматов


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

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

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

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

Полнота выходов автомата означает, что в каждом состоянии автомат выдает выходной сигнал, отличный от сигналов выдаваемых в других состояниях.

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

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




Похожие:

Алгоритм минимизации заключается в следующем iconАспектный анализ урока
Миссия методической службы в школе с углублённым изучением отдельных предметов заключается в следующем
Алгоритм минимизации заключается в следующем iconКак сформировать желание учиться?
...
Алгоритм минимизации заключается в следующем iconПротокол №4 от «08» сентября 2011г
Процесс занятий в кружке «Работа лобзиком – ажурная резьба» заключается в следующем, это этапы выполнения разнообразных видов резьбы,...
Алгоритм минимизации заключается в следующем iconПрограмма «Здоровье» моу "Аниховская сош"
Проблема здоровья детей занимает одно из главных место в воспитательной работе нашей школы. Необходимость введения этой программы...
Алгоритм минимизации заключается в следующем iconАлгоритм самооценки: в чём заключалось задание
Новизна современного урока математики заключается в организации индивидуальных и групповых форм работы. Постепенно преодолевается...
Алгоритм минимизации заключается в следующем iconС. А. Левченко Уважаемая Светлана Афанасьевна!
Этот же вопрос стал причиной для организации 17 января 2006г встречи председателями тсж и жск мотовилихинского района с депутатом...
Алгоритм минимизации заключается в следующем iconОператоры присваивания, ввода и вывода информации используются в линейном алгоритме
Линейный алгоритм алгоритм, в котором команды выполняются один раз последовательно друг за другом (линейный алгоритм)
Алгоритм минимизации заключается в следующем iconТесты для учителей информатики вариант 1 Суть такого свойства алгоритма как дискретность заключается в том, что
Алгоритм называется циклическим: а если он составлен так, что его выполнение предполагает многократное повторение одних и тех же...
Алгоритм минимизации заключается в следующем iconКонтрольная работа по теме «Алгоритмы» Вариант 1 Дать определения понятиям: алгоритм, циклический алгоритм > Найдите значение Х после выполнения алгоритма 1, если х=5
Выполнить алгоритм Занести значения переменных, изменяющихся в ходе выполнения алгоритма в таблицу
Алгоритм минимизации заключается в следующем iconАлексей Пономаренко Гуманитарная конференция 2008 Тоталитарная пропаганда 30-ых годов в фильмах
«акценты». Они могут передаваться через разговоры, действия или предметы. Мое предположение, которое я попробую обосновать, заключается...
Алгоритм минимизации заключается в следующем iconТема "Вложенные алгоритмы" Вложенный алгоритм – это алгоритм рассмотренный «под микроскопом»
...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы