35848

ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. Функционирование цифрового автомата в дискретном времени

Контрольная

Информатика, кибернетика и программирование

ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. функционирование цифрового автомата в дискретном времени. Отличительной особенностью дискретного автомата является дискретное множество внутренних состояний и скачкообразность перехода из одного состояния в другое. В реальных автоматах множество внутренних состояний всегда конечно поэтому дискретные автоматы часто называют конечными автоматами или просто автоматами.

Русский

2013-09-20

213.5 KB

6 чел.

6.21 ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. функционирование цифрового автомата в дискретном времени.

1.1. Понятие «цифровой автомат»

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

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

В реальных цифровых устройствах обработки информации в общем случае часть информации поступает на его входы в непрерывной форме (аналоговые сигналы), а часть – в дискретной, часть выходов устройства являются непрерывными, а часть – дискретными (рис. 1.1).

Рис. 1.1. Цифровое устройство обработки информации

Число входных и выходных сигналов конечно вследствие ограниченной разрядности АЦП и ЦАП, а также цифровых устройств ввода/вывода.

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

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

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

1.2. Функционирование абстрактного автомата
в дискретном времени

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

В момент времени 0Т автомат устанавливается в начальное состояние а0, и формируется функция перехода δ(а0, xj), где xj – текущий входной сигнал. Если входной сигнал в течение такта остается неизменным, то в момент времени 1Т формируется функция перехода δ(а0, xj), и автомат переходит в состояние aS, т. е. δ(а0, xj) = aS. Если входной сигнал меняется, то в момент времени 1Т δ(а0, xm) = am (рис. 1.2).

 

Рис. 1.2. Иллюстрация функционирования цифрового автомата в дискретном времени

Тогда можно записать:

δ[nT] = f(a[(n – 1)T],   x[nT]),    (1.1)

где квадратными скобками обозначен момент дискретного времени.

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

λ(t) = φ(a[nT],  x(t)),      (1.2)

где nT ≤ t < (n + 1)T.

Например, в промежутке t  [3T, 4T] функция выхода λ(t) определяется из соотношения λ(t) = φ(a[3T], x(t)). Правая граница интервала не включается, т. к. в момент времени 4T автомат совершит новый переход из состояния в состояние.

В абстрактной теории автоматов считается, что переход из состояния в состояние осуществляется мгновенно.


6.22 Описание абстрактного автомата при помощи функций переходов и функций выходов.

Представление автомата в виде «черного ящика». Математическое описание автомата

В абстрактной теории автоматов абстрагируются от способов кодирования входных/выходных сигналов и состояний и представляют их в виде букв. Цифровой автомат при этом представляют в виде «черного ящика» с одним входом и одним выходом (рис. 1.3).

Рис. 1.3. Абстрактный автомат в виде «черного ящика»

Любой автомат в общем виде описывается при помощи следующих множеств [1, 2]:

– множество входных сигналов Х;

– множество выходных сигналов Y;

– множество состояний А;

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

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

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

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

Таким образом, в общем виде автомат описывается выражением:

S = (X, Y, A, δ, λ, a0).     (1.3)

Такой автомат называют инициальным. Автомат, который описывается выражением вида

S1 = (X, Y, A, δ, λ),     (1.4)

называют неинициальным, т. е. он может начать работать с любого состояния. Примером такого автомата может быть делитель частоты.

Автомат, который описывается выражением вида

S2 = (X, Y, λ),      (1.5)

описывает комбинационную схему.

В теории автоматов используется понятие «отображение». Например, запись f: XY означает, что функция f является отображением множества Х во множество Y. Для S2 имеем: λ: XY.

Кроме того, в теории автоматов используется понятие «прямое произведение множеств», а также понятие «кортеж» – упорядоченная совокупность элементов множества. Прямое произведение двух множеств – это кортеж, состоящий из множества пар, в которых первый элемент принадлежит первому множеству, а второй элемент – второму множеству.

Рассмотрим пример.

Пусть даны два множества: X = {x1, x2}, A = {a1, a2}.

Получим прямое произведение этих множеств:

A × Y = {(a1, x1), (a1, x2), (a2, x1), (a2, x2)};   (1.6)

X × A = {(x1, a1), (x1, a2), (x2, a1), (x2, a2)}.   (1.7)

Функция переходов δ определяется как отображение прямого произведения A * X во множество А:

δ: (A × X) → A,      (1.8)

т. е. каждой паре вида (ai, xj) соответствует состояние ak: (ai, xj) → ak.

Рассмотрим пример.

Пусть даны два множества:

X = {x1, x2},    A = {a1, a2}.     (1.9)

ъ

Вычислим прямое произведение A × X и поставим каждой паре вида (ai, xj) из кортежа состояние ak:

A = A × X = {(a1, x1), (a1, x2), (a2, x1), (a2, x2)} = {a1, a2, a2, a1},       (1.10)

при этом имеем следующие соответствия:

(a1, x1)  a1;    (a2, x1)  a3;    (a1, x2)  a2;    (a2, x2)  a1. (1.11)

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

Функция выходов λ – это отображение прямого произведения A × X во множество Y,

λ: (A * X) → Y,      (1.12)

т. е. паре вида (ai, xj) соответствует выходной сигнал yn: (ai, xj) → yn.

Рассмотрим пример.

Пусть даны три множества:

X = {x1, x2},    A = {a1, a2},    Y = {y1, y2, y3}.   (1.13)

Вычислим прямое произведение A × X и поставим каждой паре вида (ai, xj) из кортежа выходной сигнал yn:

Y = A × X = {(a1, x1), (a1, x2), (a2, x1), (a2, x2)} = {y1, y2, y3, y1}, (1.14)

при этом имеем следующие соответствия:

(a1, x1)  y1;    (a2, x1)  y3;    (a1, x2)  y2;    (a2, x2)  y1. (1.15)

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

В этом случае имеем:

λ: A  Y.      (1.16)

Если функция переходов и функция выходов заданы на всех возможных парах вида (ai, xj), то такой автомат называется полностью определенным, в противном случае – частичным (частично определенным или не полностью определенным).

Если у частичного автомата не определена функция переходов хотя бы для одной пары (ai, xj), то для задания такого автомата необходимо указать множество запрещенных входных слов, т. е. последовательностей букв входного алфавита, которые переводят автомат в неопределенное состояние. Если у частичного автомата не определена только функция выходов, то запрещенные входные слова указывать не нужно.

Рассмотрим пример.

Пусть задан автомат S0:

X = {x1, x2};    A = {a1, a2, a3};    Y = {y1, y2, y3};  (1.17)

δ: (A × X) → A = {(a1, x1), (a1, x2), (a2, x1), (a3, x1), (a3, x2)} =

= {a1, a2, a3, a3, a1};     (1.18)

λ: (A × X) → Y = {(a1, x1), (a1, x2), (a2, x1), (a3, x1), (a3, x2)} =

= {y1, y2, y3, y3, y1}.     (1.19)

Данный автомат является частичным, т. к. при (a2, x2), функция перехода не определена. Слова x2x2, x1x2x2, x1x1x2x2, x1x1 … x1x2x2 являются запрещенными, если автомат установлен в состояние а1.

Пусть для автомата S1, определенного на тех же множествах X, Y, A, функции переходов и выходов имеют вид:

δ: (A * X) → A = {(a1, x1), (a1, x2), (a2, x1), (a2, x2), (a3, x1), (a3, x2)} =

= {a1, a2, a3, a1, a3, a1};    (1.20)

λ: (A * X) → Y = {(a1, x1), (a2, x1), (a2, x2), (a3, x1)} = {y1, y1, y2, y3}. (1.21)

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

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

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

6.23 Начальные автоматные языки

1.5.1. Язык регулярных выражений

Язык регулярных выражений предложен американским ученым С. К. Клини в 1956 г. и усовершенствован советским ученым В. М. Глушковым. Подробно язык регулярных выражений рассмотрен в [3, 4].

Пусть имеется автомат, установленный в начальное состояние. На вход автомата подается произвольная последовательность букв. Если автомат среди этой последовательности букв находит «знакомое» слово, то он реагирует на него выдачей определенного выходного сигнала. Реакция автомата на промежуточные последовательности букв внутри слова не важна.

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

Пусть на вход автомата S, предварительно установленного в начальное состояние a0  A, поступает слово, составленное из символов входного алфавита X, которое вызывает на выходе автомата появление символа yi  Y (рис. 6.1).

Рис. 6.1. Поступление на вход автомата слов входного алфавита

Алфавиты автомата определены следующим образом:

A = {a0, a1, … , an – 1}

X = {x1, x2, … , xk}          .                               (6.1)

Y = {y1, y2, … , yp}

Входные слова, на которые автомат откликается выходным символом yi, можно объединить во множество Hi (x1x2, … , xk). Это множество называется событием, представленным в автомате S выходным символом (буквой) yi.

Слово – конечная последовательность символов, принадлежащих некоторому множеству символов (алфавиту автомата). Если, например, алфавит Y содержит три символа y1, y2, y3, т. е.

Y = {y1, y2, y3},     (6.2)

то возможны слова y1, y1y1y1, y2y1, y3y3y2y1y2, y3, y3y1y2y1 и тд.

Пустое слово – слово нулевой длины. Пустое слово принято обозначать буквой e. Для любого слова d выполняется соотношение ed de d. Считается, что пустое слово принадлежит любому алфавиту символов. Наличие пустого слова на входе автомата означает отсутствие входных сигналов.

Событие – произвольное множество слов конечной длины, составленных из букв входного алфавита X. В дальнейшем событие будем обозначать буквой H.

Элементарное событие во входном алфавите X – это какое-либо из (+ 1)-го элементарных событий x1, x2, … , xk, e, где e – пустое слово

X = {x1, x2, … , xk}.     (6.3)

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

Полностью определенный автомат можно задать таблицей, устанавливающей соответствие между попарно непересекающимися событиями
Hi(x1, x2, … , xk) и выходными символами y1, … , yi, … , yp (табл. 6.1). Аналогичную таблицу для частичного (не полностью определенного) автомата необходимо дополнить событием Hзапр запрещенных входных слов (табл. 6.2).

Таблица 6.1

Таблица событий полностью

определенного автомата,

представленных

выходными буквами y1, y2, … , yp

Таблица 6.2

Таблица событий частичного

автомата, представленных

выходными буквами y1, y2, … , yp

Событие

Буква выходного

алфавита

Событие

Буква выходного

алфавита

H1(x1, x2, … , xk)

y1

H1(x1, x2, … , xk)

y1

H2(x1, x2, … , xk)

y2

H2(x1, x2, … , xk)

y2

Hp(x1, x2, … , xk)

yp

Hp(x1, x2, … , xk)

yp

Hзапр(x1, x2, … , xk)

Не определена

Конкатенацией (склеиванием) двух слов H1 и H2 называется слово H, которое получается в результате непосредственного слияния слова H1, стоящего слева, и слова H2, стоящего справа. Например, если

H1 = x1x2x5;      (6.4)

H2 = x4x3x4,      (6.5)

то конкатенация H1 и H2 – это слово:

H = x1x2x5x4x3x4,     (6.6)

а конкатенация H2 и H1 – это слово:

H = x4x3x4x1x2x5.     (6.7)

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

Итерацией события H называется событие [H], состоящее из пустого слова e и всех слов вида H, HH, HHH и т. д. до бесконечности. Итерация пустого события равна пустому событию: [e] = e. Итерация события H определяется так:

[H] = [e]  H  HH  HHH      (6.8)

Регулярное событие может быть задано регулярным выражением, т. е. формулой, содержащей символы e, символы входного алфавита и знаки регулярных операций над ними. Одно и то же регулярное событие может быть представлено разными эквивалентными регулярными выражениями. Для этого используются тождественные соотношения алгебры событий, которыми можно пользоваться при преобразованиях и упрощениях формул [4].

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

Регулярные выражения позволяют построить отмеченную таблицу состояний автомата Мура по методике, изложенной в [4]. В общих чертах идею перехода от регулярных выражений к табличному заданию автомата можно пояснить следующим образом. Множество событий связано с множеством выходных сигналов. Выходные сигналы автомата Мура зависят только от состояний автомата. Поэтому каждому выходному сигналу из множества выходных сигналов Y в автомате Мура можно поставить в соответствие конкретное состояние автомата Мура. Различные подмножества множества событий, которые не представляют ни одно из событий, можно считать пустым множеством событий. Если множество событий пусто, то автомат выдает пустое выходное слово e. Таким образом, если ни одно событие не наступило, автомат не выдает ни одного сигнала из множества выходных сигналов Y.

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

1.5.2. Язык граф-схем алгоритмов (язык ГСА)

Язык предложен советским ученым Л. А. Калужиным в 1959 г. ГСА – ориентированный связный граф, содержащий одну начальную вершину, одну конечную вершину, а также произвольное число операторных и условных вершин [1, 2]. В операторных вершинах стрелка всегда входит сверху и выходит снизу, а в условных вершинах – входит сверху, а выходит снизу и с одной из сторон, либо справа и слева (рис. 1.5).

Рис. 1.5. Виды вершин ГСА:
а) начальная; б) конечная; в) операторная; г) условная

ГСА должна удовлетворять следующим требованиям.

1. Выходы вершин соединяются с входами других вершин. Исключение – условная вершина, один из выходов которой может соединяться с собственным входом (возвратная вершина – рис. 1.6).

Рис. 1.6. Возвратная вершина

2. Каждый выход соединяется только с одним входом.

3. Каждый вход соединяется не менее чем с одним выходом.

4. Через любую вершину ГСА должен существовать хотя бы один путь от начальной вершины к конечной.

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

Существуют содержательные и символические ГСА. В содержательных ГСА внутри вершин записываются операторы или условие в виде:

<Переменная>: = <Значение> – для операторной вершины;

<Условие> = <Значение>?       – для условной вершины.

<Переменная> в операторной вершине – это выходной сигнал автомата.

<Значение> – эквивалент логического значения. Например, открыт/закрыт, включен/выключен.

Содержательная ГСА обычно используется на первом этапе разработки автомата, когда известно только его словесное описание. В этом случае ГСА будет графической формой словесного алгоритма работы автомата.

Далее от содержательной ГСА переходят к символьной. При этом в операторной вершине записывается один из элементов множества операторов, а в условной – одно из условий.

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


6.24 Стандартные автоматные языки

1.5.3.1. Табличный способ задания автомата

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

В отмеченной таблице переходов автомата Мура каждый столбец отмечается выходным сигналом. Кроме того, на пересечении строки xi и столбца aj записывается состояние ak, в которое перейдет автомат, находящийся в состоянии aj под действием входного сигнала xi, т. е. δ(aj, xi) = ak.

Рассмотрим пример табличного задания автомата Мура (табл. 1.1). Пусть автомат Мура имеет три входных сигнала, два выходных сигнала и три состояния.

X = {x1, x2, x3};    A = {a0, a1, a2};    Y = {y1, y2}.  (1.32)

Таблица 1.1

Отмеченная таблица автомата Мура

δ: (A × X) → A,  λ: AY

y

y1

y2

y1

     a      

  x

a0

a1

a2

x1

a1

a1

a0

x2

a0

a2

a1

x3

a2

a0

a2

Данный автомат является полностью определенным.

Рассмотрим пример табличного задания автомата Мили. Пусть автомат Мили имеет два входных сигнала, три выходных сигнала и три состояния.

X = {x1, x2, x3};    A = {a0, a1, a2};    Y = {y1, y1, y3,}.  (1.33)

В клетку таблицы переходов автомата Мили (табл. 1.2) на пересечении строки хi и столбца aj записывается состояние, в которое перейдет автомат, а в соответствующую клетку таблицы выходов (табл. 1.3) – выходной сигнал, который автомат выдает на этом переходе.

Таблица 1.2

Таблица переходов автомата Мили

δ: (A × X) → A

Таблица 1.3

      Таблица выходов автомата Мили

                         λ: (A × X) → Y

         а

  х

а0

а1

а2

        а

  х

а0

а1

а2

х1

а1

а0

а1

х1

y1

y2

х2

а0

а2

а1

х2

y1

y3

y2

«–» – значение не определено

Например, δ(а1х1) = а0 означает, что автомат, находясь в состоянии а1 при поступлении на вход сигнала х1, перейдет в состояние а0; λ(а1, х1) = y2 означает, что автомат, находясь в состоянии а1 при поступлении на вход сигнала х1, выдаст выходной сигнал y2; λ(а1, х2) = y3 означает, что автомат, находясь в состоянии а1 при поступлении сигнала х2, выдает выходной сигнал y3. Таким образом, находясь в одном и том же состоянии, автомат Мили может выдавать различные сигналы.

В этом случае совмещенная таблица переходов и выходов автомата Мили имеет следующий вид (табл. 1.4).

Таблица 1.4

Совмещенная таблица переходов и выходов автомата Мили

δ: (A × X) → A,  λ: (A × X) → Y

    а

  х

а0

а1

а2

x1

а1/y1

а0/y2

а1/–

x2

а0/y1

а2/y3

а1/y2

В клетку совмещенной таблицы переходов и выходов автомата Мили на пересечении строки хi и столбца aj записывается состояние, в которое перейдет автомат, а через косую черту – выходной сигнал, который автомат выдает на этом переходе.

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

Рассмотрим пример задания автомата Мура прямой таблицей переходов и выходов. Пусть автомат Мура имеет два входных сигнала, три выходных сигнала и три состояния.

X = {x1, x2};    A = {a0, a1, a2};    Y = {y1, y2, y3}.  (1.34)

При комбинации (а1, x2) не определены функция переходов  = (а1) и функция выходов = (а1), см. табл. 1.5.

Таблица 1.5

Прямая таблица переходов и выходов автомата Мура

δ: (A × X) → A,  λ: AY

Исходное

состояние аi

Входной

сигнал xk

Следующее

состояние аj,

= (аi)

Выходной

сигнал yn,

= (аi)

а0 

x1

а1

y1

а0

x2

а0

y1

а1

x1

а2

y3

а1

x2

а2

x1

а1

y1

а2

x2

а0

y1

В процессе структурного синтеза на основе данной таблицы строится кодированная прямая таблица переходов и выходов автомата (табл. 1.6). При этом столбец 3 будет представлять собой исходные данные для формирования функции возбуждения элементов памяти автомата, имеющей различный вид при реализации памяти автомата на D-триггерах и на JK-триггерах.

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

Таблица 1.6

Прямая кодированная таблица переходов и выходов автомата Мили

δ: (A × X) → A,  λ: (A × X) → Y

Исходное

состояние аi 

Входной

сигнал xk

Следующее

состояние аj,

= (аi)

Выходной

сигнал yn,

= (аi , xk)

а0 (код 00)

x1

а1 (код 01)

y1

а0 (код 00)

x2

а2 (код 10)

y2 

а1 (код 01)

x1

а2 (код 10)

y2

а1 (код 01)

x2

а1 (код 01)

x1

а1 (код 01)

y3

а2 (код 10)

x2

а0 (код 00)

y1

1.5.3.2. Задание автомата с помощью орграфа

Для графического задания автомата на стандартном языке используется орграф – ориентированный связный граф с одним типом вершин и однонаправленными дугами. Вершины соответствуют состояниям, а дуги – переходам. В автомате Мура дуга отмечается входным сигналом, а в автомате Мили – входным сигналом и через косую черту – выходным сигналом на этом переходе. Если в автомате Мили выходной сигнал на переходе отсутствует, то над дугой после косой черты ставится прочерк. Если переход безусловный, то вместо входного сигнала в автомате Мили ставят прочерк, в автомате Мура – «1» или прочерк. Если переход вызывается несколькими входными сигналами, то они объединяются по ИЛИ. Кроме того, в автомате Мура каждая вершина отмечается выходным сигналом.

Из орграфа автомата Мура (рис. 1.7, а) видно, например, что в состоянии a0 автомат выдает выходной сигнал y1, при получении входного сигнала x1 остается в том же состоянии, а при получении входного сигнала x3 переходит в состояние a2, в котором выдает выходной сигнал y2.

Из ографа автомата Мили (см. рис. 1.7, б) видно, например, что в состоянии a0 автомат при получении входного сигнала x1 выдает выходной сигнал y2 и остается в том же состоянии, при получении входного сигнала x2 переходит в состояние a2, выдавая при этом выходной сигнал y1.

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

Рис. 1.7. Орграф автомата: а) Мура; б) Мили

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

б)

x3/y1

y2

x2/y1

y2

x1/y3

x1/–

a3

a1

x2/y1

x3/y1

x1/y1

x1/y2

a1

a2

a0

а)

x3

y2

y3

y2

y1

x1  x2

 x1

a3

a1

x3

x2

x1

x1

a1

a2

a0

X = x1, x2, ... , xk

Y = y1, y2, ... , yp

Автомат

A = a0, ... , an – 1

Условие

г)

Условие

в)

б)

Оператор

Конец

Начало

а)

X = x1, x2, ... , xk

Y = y1, y2, ... , yp

A = a0, ... , an – 1

δ(a0, xj) = as

δ(a0, xn) = ag

δ(am, xj) = ap

Переход в ak

Переход в am

Установка

a0

ys = λ(ak, xk)

ym = λ(am, xj)

yf  = λ(am, xm)

yk = λ(a0, xn)

Функция выходов

xj

Состояние

xk

xn

xm

xj

Буква

входного алфавита

Функция переходов

δ(ak, xk) = an

am

yi = λ(a0, xj)

δ(a0, xm) = am

δ(a0, xn) = ag

ak

a0

. . .

t

nТ

1Т

2Т

0Т

Непрерывная (аналоговая) информация

ЦАП

Y

X

Внешняя среда

Дискретная информация

Дискретная информация

Дискретная информация с цифровых устройств

Дискретная информация

Непрерывная (аналоговая) информация

АЦП

Устройство обработки

дискретной

информации