Способы задания автоматов


Понятие конечного детерминированного автомата

Автоматы можно рассматривать как механизмы, состоящие из:

  • блока управления, который может пребывать в различных состояниях (S внутренний алфавит);
  • входного канала;
  • выходного канала.

Входной канал считывает входные сигналы (Х) из внешней среды. Выходной канал выдает выходные сигналы (Y) во внешнюю среду. Работа автомата протекает в дискретные такты времени t=1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .

Определение. К.Д.А. называется система , где - алфавит состояний, – входной алфавит, – выходной алфавит. Множества S, X, Y – конечные.

– функция переходов,

– функция выходов.

Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным.

Способы задания автоматов

    1. Таблица переходов–выходов.
S\X
         
M          
       
M          
         
    1. С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .

      Этой дуге приписывается пометка :

Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.

  1. С помощью канонических уравнений:

в момент t=1 автомат находится в начальном состоянии . В каждый момент t=1,2,3,… дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала выдает выходной сигнал из множества Y, согласно функции выходов l , а затем меняет свое состояние на s(t+1) согласно функции переходов d.

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

После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях , , ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом "запомнить". В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t.

Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:

Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:

={"на первом такте поступил 0"};

={"на первом такте поступила 1"}.

И –начальное состояние.

Построим таблицу переходов–выходов:

 

 


Для нарисуем диаграмму Мура:

И дополним таблицу переходов–выходов:


Лекция 4.



Дата добавления: 2020-12-11; просмотров: 362;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.