Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Виды автоматов

Автомат имеет следующие составляющие:

  • 1) входные переменные, которые представляют собой воздействия, генерируемые извне и влияющие на поведение исследуемой системы;
  • 2) выходные переменные, называемые реакцией системы, представляющие собой величины, характеризующие поведение данной системы.

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

Предполагается, что любая система, представляемая основной моделью, управляется некоторым синхронизирующим источником. Все переменные системы изменяются в определенные дискретные моменты времени, в которые подается синхронизирующий сигнал. Эти моменты времени называются тактами (тактовыми моментами) и обозначаются буквой ts. Тогда поведение системы в любой момент времени не зависит от интервала времени между и ts_l. Кроме того, независимой величиной, относительно которой определяются все переменные системы, является не время, а порядковый номер, связанный с тактом. Системы, удовлетворяющие вышеизложенным предположениям, называются синхронными. Асинхронные же системы, меняют свои сигналы, не привязываясь к синхронизирующему сигналу.

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

  • 1. В устройствах первого типа набор выходных сигналов, вырабатываемых в момент времени (Г + ДО, зависит только от набора входных сигналов, поданных в момент времени /, и не зависит от сигналов, поступивших на входы автомата в предшествующее время. Интервал Д/ — время реакции автомата. Он остается одинаковым для исходного / при любых допустимых наборах входных сигналов. Такое однозначное и неизменное во времени соответствие между наборами входных и выходных сигналов обусловливается неизменностью внутреннего состояния автоматов и независимостью этого состояния от внешнего воздействия. Устройства такого типа называют автоматами без памяти.
  • 2. В автоматах второго типа набор выходных сигналов, вырабатываемый в некоторый дискретный момент времени, зависит не только от сигналов, поданных в тот же момент времени, но и от сигналов, поступивших ранее. Эти предшествующие внешние воздействия фиксируются в автомате путем изменения его внутреннего состояния. Таким образом, реакция данного автомата однозначно определяется поступившим набором входных сигналов и его внутренним состоянием на данный момент времени. Этими же факторами однозначно определяется и то состояние, в которое автомат перейдет.

Конечным автоматом называется объект, имеющий конечное число входов, конечное число внутренних состояний, работа которого носит детерминированный (от англ. — «определенный») характер. Если конечный автомат снабдить внешней памятью и допустить ее неограниченное расширение, то такая система будет принадлежать к автоматам третьего типа, например машина Тьюринга. Он показал, что с помощью автоматов третьего типа может быть смоделирована любая система, т.е. реализован любой алгоритм по переработке информации.

Таким образом, можно определить конечный автомат как устройство, определенное конечным множеством состояний входов — Р = {р,, р2, ..., рдг}, конечным множеством состояний выходов — Л = {А,|, Х2, ^}, конечным множеством внутренних состояний —

^ = {?], $2, •••> а также функцией переходов, определяющей порядок смен внутренних состояний (ср), и функцией выходов, задающей выходные состояния в зависимости от Р и 5 (|/):

*у = (р, ?, Л, Ф, |/, 50).

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

Будем предполагать, что автомат функционирует в некоторые дискретные моменты времени (такт). Время, в течение которого не происходит изменения входного сигнала р, обозначается через Т и в зависимости от того, чем определяется длительность этого интервала, будем различать два класса автоматов: синхронные и асинхронные. Функционирование или поведение автомата при заданных множествах (Р, Л, X) и начальном внутреннем состоянии х0 полностью детерминировано и определяется функциями переходов

И ВЫХОДОВ ф, ф.

Функция переходов устанавливает зависимость внутреннего состояния автомата в следующий момент времени от состояния входа и внутреннего состояния в настоящий момент времени.

Функция выходов устанавливает зависимость состояния выхода автомата от состояния входа и внутреннего состояния автомата.

Различный характер этих зависимостей для различных автоматов позволяет выделить отдельные типы автоматов в классе синхронных конечных детерминированных автоматов.

Основными являются две модели: Мили и Мура (рис. 6.1).

Автоматы Мили (а) и Мура (б)

Рис. 6.1. Автоматы Мили (а) и Мура (б)

Автомат Мили описывается следующими формулами:

1) внутреннее состояние автомата в следующий момент времени зависит от внутреннего состояния автомата в настоящий момент времени и входного сигнала в настоящий момент времени:

x(t + 1) = ф(х(/), р(0);

2) выходной сигнал автомата в настоящий момент времени зависит от входного сигнала в настоящий момент времени и внутреннего состояния автомата в настоящий момент времени:

МО = У(*(0» 9(0)-

Понятие состояния автомата в момент времени t определяется внутренним состоянием автомата и состоянием входа автомата в тот же момент времени:

М(0 = Ш, Р(0).

Автоматы, для которых функции переходов ф и функции выходов г определены на всех парах (р, х), называются полностью определенными или полными автоматами. Соответственно, автоматы, для которых функции переходов или функции выходов определены не на всех парах (р, х), называются недоопределенными (не полностью определенными) автоматами. Состояние M(t) автомата, недоопределенного на соответствующей паре (р, х), называется неиспользованным состоянием автомата. Если на каком-либо определенном состоянии автомата не определена только функция выходов, то говорят, что ему соответствует безразличное состояние выхода.

Для автомата Мура функции переходов и выходов выглядят следующим образом:

x(t + ) = ф(х(/), р(0);

X(t + 1) = |f(x(t + 1)) = |/(ср(х(0, Р(0) = V'(*(0, р(ОХ

Функция выходов для автомата Мура определяется внутренним состоянием автомата.

Для асинхронного автомата поведение определяется следующими уравнениями:

x(t + 1) = ф(х(/), р(t + 1));

А,(/ + 1) = f(x(t + 1), р(? + 1)).

В асинхронном автомате изменение состояния входа вызывает переход в следующее внутреннее состояние, т.е. внутреннее состояние автомата зависит от состояния входа в этот же момент времени; соответственно, состояние выхода автомата зависит от состояния его входа.

Если рассматривать автомат с учетом его внутренних состояний, то необходимо определить функции перехода (из внутреннего состояния Xj во внутреннее состояние Хр не исключая / = у). Задание функций выходов означает, что каждой паре (р, , х,-) поставлено в соответствие состояние выхода . Языки, позволяющие таким образом описать автомат, называются стандартными языками. К стандартным языкам относятся таблицы переходов, таблицы выходов, матрицы переходов, таблицы включений, графы переходов.

 
<<   СОДЕРЖАНИЕ   >>