Способы задания автоматов
Понятие конечного детерминированного автомата
Автоматы можно рассматривать как механизмы, состоящие из:
- блока управления, который может пребывать в различных состояниях (S внутренний алфавит);
- входного канала;
- выходного канала.
Входной канал считывает входные сигналы (Х) из внешней среды. Выходной канал выдает выходные сигналы (Y) во внешнюю среду. Работа автомата протекает в дискретные такты времени t=1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .
Определение. К.Д.А. называется система , где - алфавит состояний, – входной алфавит, – выходной алфавит. Множества S, X, Y – конечные.
– функция переходов,
– функция выходов.
Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным.
Способы задания автоматов
- Таблица переходов–выходов.
S\X | … | … | |||
M | |||||
M | |||||
- С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .
Этой дуге приписывается пометка :
Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.
- С помощью канонических уравнений:
в момент t=1 автомат находится в начальном состоянии . В каждый момент t=1,2,3,… дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала выдает выходной сигнал из множества Y, согласно функции выходов l , а затем меняет свое состояние на s(t+1) согласно функции переходов d.
Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.
После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях , , ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом "запомнить". В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t.
Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:
Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:
={"на первом такте поступил 0"};
={"на первом такте поступила 1"}.
И –начальное состояние.
Построим таблицу переходов–выходов:
Для нарисуем диаграмму Мура:
И дополним таблицу переходов–выходов:
Лекция 4.
Дата добавления: 2020-12-11; просмотров: 362;