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

y (t) =(a (t), x (t));

a (t+1) = δ (a (t), x (t)). (1-1)

Автомат Мура - системой уравнений:

a (t+1) = δ (a (t), x (t)). (1-2)

С-автомат - системой уравнений:

y 1 (t) =(a (t),x (t));

У 2 (t) = 2 (a (t));

a (t+1) =δ (a (t),x (t)).

Произвольный абстрактный автомат Мили или Мура (рис.1.1.) имеет один входной и один выходной каналы. Произвольный абстрактный С-автомат имеет один входной и два выходны х канала (рис.1.2.).

Рисунок 1.1 - Абстрактный автомат

Рисунок.1.2 Абстрактный С-автомат

Если на вход абстрактного автомата Мили или Мура, установленного в начальное состояние а о, подавать буква за буквой некоторую последовательность букв входного алфавита х (0), х (1),. - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у (0), у (1),. - выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y 1 (0), y 1 (1),. и y 2 (0), y 2 (1),. В абстрактном С - автомате выходной сигнал y 2 (t) =(a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y 1 (t) =λ 1 (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).

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

Выделяют полностью определенные и частичные автоматы.

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (x i ,a j).

Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (x i ,a j).

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

1.3 Способы задания абстрактных автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,,,a o }. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся на пересечении строки, отмеченной входным сигналом x i , и столбца отмеченного состоянием a j , ставится состояние а k , являющееся результатом перехода автомата из состояния a j под воздействием входного сигнала х i , что определяется выражением a k =(a j , х j).

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

Состояния
входные сигналы
				(а к, х j)

Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х 1 , х 2 } - и алфавитом состояний A={a 1 , a 2 , а 3 } представлен в табл.1.2.

Таблица 1.2

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

Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.

Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом X j , и столбца, отмеченного состоянием а к, ставится выходной сигнал У m , который автомат выдает, находясь в состоянии а k при наличии входного сигнала Xj, что определяется выражением Ym=(а k , х j).

Таблица 1.3 Таблица выходов абстрактного автомата Мили.

Состояния
Входные сигналы

Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x 1 , x 2 }, алфавитом состояний A={a 1 , а 2 , а 3 } и выходным алфавитом Y={y 1 , y 2 , y 3 }-представлен в табл.1.4.

Таблица 1.4

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

На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).

Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.

Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой а j и строки, помеченной буквой a s автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.

Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).

Таблица 1.6

Состояния
Входные сигналы
		 (a 2 , x j)		 (а k , x j)
		 (a 2 , x j)		 (а k , x j)

Таблица 1.7

Таблица 1.9.

При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины a k и a s соединяются дугой в том случае, если в автомате имеется переход из состояния a k в состояние a s . Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).

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

Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура

При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:

S={ X,A,Y,F}, где F задает для каждого состояния а j автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата а j указывается отображение F ai , представляющее собой множество всех троек а р, x m , y k , и таких, что под воздействием входного сигнала x m автомат переходит из состояния а j в состояние а р, выдавая при этом выходной сигнал y k .

Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций δ и λ в соответствии с выражением: a p = δ (a i , x m), y к = λ (a i , x m).

Отображение F ai записывается следующим образом:

F ai {a p (X m /y k),a i (X f /y z) …}.

Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:

S={ X,A,Y,F}, X={x 1 ,x 2 }, A={a 1 , а 2 , а 3 }, Y={y 1 , y 2 , у 3 },

F a1 ={a 2 (x 1 /y 2), a 1 (x 2 /у 3) },

F а 2 ={а 3 (x 1 /y 3), a 1 (x 2 /y 1) },

F a 3 ={a 1 (x 1 /y 3), а 2 (x 2 /y 2) }.

Следует отметить, что функция F ai всегда записывается для исходного состояния.

Определим синхронные и асинхронные автоматы. Состояние а s автомата S называется устойчивым cостоянием, если для любого входного сигнала х j Х, такого, что а s = δ (а i Х m) имеет место a s = δ (a s , x m).

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

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

26 апреля 2010 в 19:06

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2

• Электроника для начинающих

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

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

Электронные цифровые схемы формально можно разделить на 2 класса:

• Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
• Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

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

Абстрактный автомат

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

Или, если перейти от иллюстрации к математическому описанию:
A =

Обозначения:

1. Множество {A} – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
2. Множество {B} – представляет собой множество значений на физических выходах автомата.
3. Множество {C} – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.
4. δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
5. λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

δ и λ не показаны на схеме для визуального упрощения.

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

Выделяют 2 типа автоматов:

1. Автоматы Мили. Описывается системой уравнений:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t-1)).
2. Автоматы Мура. Описывается уравнениями:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t)).

Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала .
Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).
Так же можно отметить, что от одного типа можно перейти ко второму и наоборот, причем при переходе от автомата Мили к автомату Мура число внутренних состояний автомата останется прежним, а при обратном переходе число внутренних состояний может возрасти. На этом останавливаться подробно не будем, считая, что синтезировали(нарисовали граф) автомат того типа, который надо.
Итак, на этом с матчастью окончено. Попробуем описать автоматы.

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

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

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

Есть два основных способа задания автомата:

1. При помощи графов.
2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

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

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

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным . Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным , а автомат Мура – частичным .
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным . Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.

Таблицы переходов и выходов.

Графы нагляднее для человека, а таблицы - для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

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

Пример синтеза автомата

При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:

Кодируем входной и выходной алфавиты:
A = {a0, a1}, где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = {b0, b1}, где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:


Вот такая забавная чебурашка получилась:-). Теперь можно построить таблицу переходов и выходов:

Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить:

Нанесём полученную функцию на карту Вейча и минимизируем:

Выпишем, что получилось:

Строим по функции схему (Выполняли домашнее задание?).

Имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита , на выходе оно выдаёт символы (в общем случае) другого алфавита.

Формально абстрактный автомат определяется как пятерка

$\backslash boldsymbol\{A\; =\; (S,\; X,\; Y,\; \backslash delta,\; \backslash lambda)\}$

Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат .

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата $\backslash boldsymbol\{s\_1s\_2s\_3...\}$ и последовательности выходных символов $\backslash boldsymbol\{y\_1y\_2y\_3...\}$, которые для последовательности символов $\backslash boldsymbol\{x\_1x\_2x\_3...\}$ разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений: $\backslash boldsymbol\{s(t+1)=\backslash delta(s(t),x(t));\}$

$\backslash boldsymbol\{y(t)=\backslash lambda(s(t),x(t)).\}$

Для уточнения свойств абстрактных автоматов введена классификация .

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

Напишите отзыв о статье "Абстрактный автомат"

Отрывок, характеризующий Абстрактный автомат

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

Кутузов, сопутствуемый своими адъютантами, поехал шагом за карабинерами.
Проехав с полверсты в хвосте колонны, он остановился у одинокого заброшенного дома (вероятно, бывшего трактира) подле разветвления двух дорог. Обе дороги спускались под гору, и по обеим шли войска.
Туман начинал расходиться, и неопределенно, верстах в двух расстояния, виднелись уже неприятельские войска на противоположных возвышенностях. Налево внизу стрельба становилась слышнее. Кутузов остановился, разговаривая с австрийским генералом. Князь Андрей, стоя несколько позади, вглядывался в них и, желая попросить зрительную трубу у адъютанта, обратился к нему.
– Посмотрите, посмотрите, – говорил этот адъютант, глядя не на дальнее войско, а вниз по горе перед собой. – Это французы!
Два генерала и адъютанты стали хвататься за трубу, вырывая ее один у другого. Все лица вдруг изменились, и на всех выразился ужас. Французов предполагали за две версты от нас, а они явились вдруг, неожиданно перед нами.
– Это неприятель?… Нет!… Да, смотрите, он… наверное… Что ж это? – послышались голоса.
Князь Андрей простым глазом увидал внизу направо поднимавшуюся навстречу апшеронцам густую колонну французов, не дальше пятисот шагов от того места, где стоял Кутузов.
«Вот она, наступила решительная минута! Дошло до меня дело», подумал князь Андрей, и ударив лошадь, подъехал к Кутузову. «Надо остановить апшеронцев, – закричал он, – ваше высокопревосходительство!» Но в тот же миг всё застлалось дымом, раздалась близкая стрельба, и наивно испуганный голос в двух шагах от князя Андрея закричал: «ну, братцы, шабаш!» И как будто голос этот был команда. По этому голосу всё бросилось бежать.
Смешанные, всё увеличивающиеся толпы бежали назад к тому месту, где пять минут тому назад войска проходили мимо императоров. Не только трудно было остановить эту толпу, но невозможно было самим не податься назад вместе с толпой.
Болконский только старался не отставать от нее и оглядывался, недоумевая и не в силах понять того, что делалось перед ним. Несвицкий с озлобленным видом, красный и на себя не похожий, кричал Кутузову, что ежели он не уедет сейчас, он будет взят в плен наверное. Кутузов стоял на том же месте и, не отвечая, доставал платок. Из щеки его текла кровь. Князь Андрей протеснился до него.
– Вы ранены? – спросил он, едва удерживая дрожание нижней челюсти.
– Раны не здесь, а вот где! – сказал Кутузов, прижимая платок к раненой щеке и указывая на бегущих. – Остановите их! – крикнул он и в то же время, вероятно убедясь, что невозможно было их остановить, ударил лошадь и поехал вправо.

Тема 5.1. Переработка информации с помощью конечных автоматов

Глава 5. Основы теории конечных автоматов

Резюме по теме

Вопросы для повторения

1.Маршрут это?

2.В каком случае маршрут называется циклическим?

3.Что представляет собой цепь?

4.В каком случае цепь является простой цепью?

5.Дайте определение Эйлерова цикла?

6.В чем заключается отличие Эйлерова и Гамильтонова циклов?

7.Когда граф называется деревом?

8.Чем являются связные компоненты леса?

9.Вершина называется концевой если?

В данной теме рассмотрены такие понятия как маршрут, цикл, цепь, контур и так далее применительно графов. Приведены Эйлеров и Гамильтонов циклы. Показана отдельная структура графов, которая определяется как дерево. Совокупность данных структур характеризуется как лес.

Цель : рассмотреть основы теории конечных автоматов.

Задачи :

1. Рассмотреть понятие абстрактного автомата.

2. Выявить способы задания автоматов.

3. Рассмотреть взаимосвязь между автоматами Миля и Мура.

Автомат - дискретный преобразователь информации, способный под действием входных сигналов переходить из состояния в состояние и вырабатывать выходные сигналы.

Абстрактный автомат задается с помощью следующей пятерки множеств:

А = { X, Y, S, d , l} ,

где Х = {X 1 , X 2 ... X M } – входной алфавит автомата или множество входных символов;

Y = {Y 1 , Y 2 ... Y N } – выходной алфавит автомата или множество выходных символов;

S = {S 0 , S 1 . . . S K-1 } – алфавит или множество внутренних состояний автомата;

S 0 – начальное состояние автомата (в момент времени t = 0 ).

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

l - функция выходов автомата.

Автомат называется конечным автоматом , если множества X, Y, S конечны (или счетны).

Автомат функционирует в дискретные моменты времени t = 0, 1, 2 ...n (рис. 5.1).

Рис. 5.1. Конечный автомат

В каждый момент времени автомат находится в одном из состояний из множества S .

Функция переходов d t следующее состояние автомата в зависимости от текущего состояния и входного сигнала или символа входного алфавита. Другими словами, функция d каждой паре «состояние – входной сигнал» ставит в соответствие следующее состояние.

d: S´X ® S; d - есть отображение декартова произведения S´X в S .

Функция переходов может быть записана следующим образом: S t+1 = d(S t , X t) .

Функция выходов l определяет в каждый момент времени t выходной сигнал автомата.

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

Y t = l (S t , X t) - для автомата Мили, или l: S´X®Y .

Y t = l (S t) - для автомата Мура.

В автомате Мили выходной сигнал в момент времени t зависит как от входного сигнала в момент времени t , так и от текущего состояния.

В автомате Мура выходной сигнал явно от входного не зависит и определяется только текущим состоянием.

Состояние автомата – это память автомата о прошлых входных воздействиях.

Автоматы также называют последовательностными машинами (Sequential Machines), так как входная последовательность преобразуется в последовательность состояний и выходную последовательность.

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

Слово или цепочка – это конечная последовательность символов (букв) входного алфавита. Должны выполняться следующие условия (условия автоматности):

1. Длины входных и выходных слов одинаковы;

2. Одинаковым начальным отрезкам входных слов соответствуют одинаковые начальные отрезки выходных слов.