22107

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

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

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

Русский

2013-08-04

28 KB

33 чел.

Лекция 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. В автомате, обладающем полной системой переходов, в каждом столбце таблицы переходов должны встречаться все состояния.

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

12319. Саясаттану пәні бойынша дәріс сабақтарының контактілік мәліметтері Контактілік дәріс сабақтарының кестесі 274.5 KB
  Саясаттану пәні бойынша дәріс сабақтарының контактілік мәліметтері Контактілік дәріс сабақтарының кестесі Тақырыптар Сағат саны 1 Тақырып1.Саясаттану ғылым және оқу пәні. ...
12320. Конвенция о правах ребенка 79 KB
  Конвенция ООН о правах ребёнка — международный правовой документ, определяющий права детей на образование, пользование достижениями культуры, правом на отдых и досуг, и оказание иных услуг детям государствами-членами ООН.
12321. Состояние имиджа интернет-магазина 6cotok.ru и пути его совершенствования 654.5 KB
  Благодаря «имиджу», появилась такая профессия, которая приобретает популярность, как «имиджмейкер». Имиджмейкер – это специализированный сотрудник по связям с общественностью, который разрабатывает и создает специальные рекламные мероприятия, для повышения имиджа организации.
12322. Саясаттанудың заңдары мен категориялары, әдістері мен функциялары 284.5 KB
  САЯСАТТАНУ ҒЫЛЫМ РЕТІНДЕ Саясаттанудың объектісі мен пәні Саясаттанудың заңдары мен категориялары әдістері мен функциялары 1. Саясатты түсіну ежелден бастау алады. Оны ғылыми тұрғыда шешу кейінгі ғасырларға келеді. Саяси ғылым қазіргі кездегі мәнін Х...
12323. Никола Макиавелли 25.77 KB
  СӨЖ Тақырыбы: Никола Макиавелли Никола Макиавелли Қайта өрлеу дәуірінің көрнекті өкілі буржуазиялық саяси ілімінің негізін қалаушы Никола Макиавелли саяси қайраткер дипломат және тарихшы ретінде де кеңінен танылады. Мемлекет және құқық концепциясы тарихын
12324. Әлемдік әлеуметтанудың қалыптасуы мен даму тарихы 132.16 KB
  ІІ дәріс. Әлемдік әлеуметтанудың қалыптасуы мен даму тарихы. 1. Антикалық және Ортағасыр дәуіріндегі әлеуметтік ойлар. 2. Жаңа заман мен Ағартушылар дәуіріндегі әлеуметтік тұжырымдамалар. 3. Әлеуметтану ғылымының классика...
12325. Саясаттану пәнінен 1-аралық бақылау сұрақтары 43.18 KB
  Саясаттану пәнінен 1аралық бақылау сұрақтары Саясаттану ғылым ретінде Саясаттану ғылымының атқаратын қызметтері Саяси ойшылдардың саясатқа берген анықтамалары Саясаттанудың деңгейлері Саясаттанудың парадигмалары Ежелгі дәуірдегі саяси ойшылд
12326. Эмпирикалық әлеуметтану бойынша глоссарий 15.16 KB
  Эмпирикалық әлеуметтану бойынша глоссарий Эмпирикалық әлеуметтану нақты зерттеулер жүргізуді осылардың негізінде арнаулы әдістер қолдану сұрау бақылау тәжірибе арқылы жаңа фактілерді жинап талдауды қорытындылауды айтады Интервью көсемсөз жанры журналист
12327. Тақырыбы: Томас Джефферсонның саяси-құқықтық көзқарасы 43.85 KB
  СӨЖ Тақырыбы: Томас Джефферсонның саясиқұқықтық көзқарасы АҚШ тарихы ХVІІІ ғасырдың соңғы ширегі мен ХІХ – ғасырлардың басында әлемге көрнекті саңлақтар тобын берді. Олар әр қилы көзқарасты ұстанып әр түрлі партиялардың құрамында болғанымен барлығы да америка