6 Основные понятия и определения теории абстрактных авто­матов (лекция №9)
Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму. Примерами ЦА могут служить живые организмы, процессоры, бытовая техника калькуляторы – это реальные устройства, а также есть абстрактные, например, модели алгоритмов. ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем , что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние . Для того чтобы хранить данные о состоянии, в котором находится устройство в ЦА используются запоминающие элементы – триггеры.
6.1 Математическая модель цифрового автомата
Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воз­действием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а 1) у которого:

1. 
   A={a 1 , a 2 , ... ,a m } – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.
2. 
   X={x 1 , x 2 , ... ,x f } – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например , если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.
3. 
   Y={y 1 , y 2 , ..., y g } – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.
4. 
   : AXA – функция переходов a(t+1)=  (x(t),a(t)) . Функция переходов определяет, в какое состояние a(t+1) перейдет автомат под воздействием входного сигнала x(t) , если в текущий момент времени автомат находится в состоянии a(t).
5. 
    : AZW – функция выходов y (t )=  (a (t ), x (t )). Функция выходов определяет какое выходное значение y (t ) будет установлено на выходе автомата в зависимости от входного значения x (t ) и текущего состояния a (t ) .
6. 
   a i  A - начальное состояние автомата –состояние в которое устанавливается ЦА после подачи питания или после сброса

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

Абстрактный автомат (рисунок 6.1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата , причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита X(t)  Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=, a(t)  A, y(t)  Y.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где  - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рисунок 6.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

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

6.2 Классификация цифровых автоматов

Рассмотренные выше абстрактные автоматы можно разделить на:

1. 
   полностью определенные и частичные;
2. 
   детерминированные и вероятностные;
3. 
   синхронные и асинхронные;

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

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находя­щийся в некотором состоянии a i , под действием любого входного сигнала z j не может перейти более, чем в одно состоя­ние.

В противном случае это будет вероятностный автомат , в котором при заданном состоянии a i и заданном входном сиг­нале z j возможен переход с заданной вероятностью в различные состояния.

Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния . Состояние a s автомата называется устойчивым, если для любого состояния a i и входного сигнала z j таких, что (a i , z j) = a s имеет место (a s , z j) = a s , т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала z k , отличного от z j .

Автомат, у которого все состояния устойчивы - асинхронный .

Автомат называется синхронным , если он не является асинхронным.

Абстрактный автомат называется конечным , если конечны множества А = {a 1 , a 2 , ..., a m }, Z = {z 1 , z 2 , ..., z f }, W = {w 1 , w 2 , ..., w g }. Автомат носит название инициального , если в нем выделено начальное состояние a 1 .
6.3 Разновидности цифровых автоматов
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

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

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов  1 и  2 , каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а(t+1) =(a(t), z(t)); w(t) = 1 (a(t), z(t)); u(t) =  2 (a(t)); t = 0, 1, 2, ...
Выходной сигнал U h = 2 (a m) выдается все время, пока автомат находится в состоянии a m . Выходной сигнал Wg= 1 (a m , z f) выдается во время действия входного сигнала Z f при нахождении автомата в состоянии a m .
7 Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а 1). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций  и  (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графиче­ский.
7.1 Табличный способ описания цифровых автоматов

При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов.

Таблица переходов отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения , которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала x i (которому соответствует i-й столбец) из состояния a j (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2

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

y 2

Рисунок 6.7 –Графическое представление автомата Мура

Рисунок 6.8 –Графическое представление автомата Мили

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

8.1 Структура цифрового автомата

Внутреннюю структуру цифрового автомата можно изобразить, как показано на рисунке 8.1.

Рисунок 8.1 – Структурная схема цифрового автомата.

Блок памяти представляет собой набор триггеров, которые хранят разряды закодированного номера состояния. Количество триггеров зависит от количества состояний, в которых может находиться автомат. И вычисляется как:

N=log 2 M
где M – количество состояний, а N –количество триггеров
Комбинационная схема №2 реализует функцию выходов автомата и на ее выходе устанавливаются выходные значения автомата в соответствии с текущим состоянием автомата и входными значениями.

8.2 Минимизация числа состояний цифрового автомата
Часто при выполнении абстрактного синтеза вводятся избыточные состояния, эквивалентность которых не является очевидной. Избыточное количество состояний может привести к применению лишних триггеров, что усложнит КС1 и КС2. Поэтому очень важно выполнять минимизацию числа состояний перед его структурным синтезом.

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

Определение Два состояния a s и a m являются эквивалентными, если
 (a s , E) =  (a m , E), где  - функция перехода, E – входное слово произвольной длины.

Другими словами, состояния эквивалентны, если в ответ на одни и те же входные слова вырабатывается одна и та же последовательность состояний, независимо от того в каком из двух состояний a s или a m находился автомат в начальный момент времени. Если два состояния эквивалентны , то одно состояние можно заменить на другое.

Кроме эквивалентных состояний существует понятие k-эквивалентных состояний: 1-эквивалентные, 2-эквивалентные и т.д.

Определение Два состояния a s и a m являются k - эквивалентными, если
 (a s , E k ) =  (a m , E k ), где  - функция перехода, E k – входное слово длины k .
Алгоритм минимизации:

1. 
   Находится последовательно разбиения П 1 , П 2 , … П К, П К+1 состояний автомата до тех пор пока на каком-то К+1 шаге П К.+1 станет равно П К. В этом случае полученное к-эквивалентное разбиение будет представлять собой полностью эквивалентные классы.
2. 
   В каждом классе эквивалентности выбирают по одному состоянию, которые образуют новое множество состояний минимизированного автомата.
3. 
   Для переопределения функций переходов и выходов вычеркивают строки, которые соответствую состояниям , не вошедшим в новое множество состояний минимизируемого автомата, а в остальных строка таблицы переходов все состояния заменяются на им эквивалентные состояния, которые вошли в новое множество.
4. 
   Если множество состоит из одного состояние, то у него нет эквивалентных состояний. Если все состояния входят в отдельные множества из одного состояния, то автомат нельзя минимизировать.
5. 
   Разбиение на множества начинается с 0-эквивалентного класса. В данном случае в одни множества попадают состояния с одинаковыми выходными сигналами.

На выходе оно выдаёт символы (в общем случае) другого алфавита.

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

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

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

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата и последовательности выходных символов , которые для последовательности символов разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

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

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

Wikimedia Foundation . 2010 .

• Диаграмма состояний (теория автоматов)
• Нагорный Карабах

Смотреть что такое "Абстрактный автомат" в других словарях:

абстрактный автомат - abstraktusis automatas statusas T sritis automatika atitikmenys: angl. abstract automaton vok. abstrakter Automat, m rus. абстрактный автомат, m pranc. automate abstrait, m … Automatikos terminų žodynas

Автомат - В Викисловаре есть статья «автомат» Автомат: Автомат устройство, самостоятельно выполняющее некоторые действия … Википедия

Конечный автомат - Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например,… … Википедия

ТЬЮРИНГА, МАШИНА - Абстрактный автомат (то есть компьютер или другой точный, определенный механизм), теоретически охарактеризованный британским математиком Аланом М. Тьюрингом в 1930 х гг. В основном, машина Тьюринга состоит из ленты и считывающей головки. Лента… … Толковый словарь по психологии

Теория автоматов

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

теория автоматов - Раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными понятиями этой теории… … Справочник технического переводчика

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

Компьютер - Схема персонального компьютера: 1. Монитор 2. Материнская плата 3 … Википедия

Формальные методы - Пример формальной спецификации с использованием Z нотации В информатике и инженерии программного обеспечения формальными методами называется группа техник, основанных на математическом аппарате для … Википедия

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 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)).

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

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

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

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

Графы

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

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

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

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

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

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

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

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


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

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

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

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

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

1.1 Основные понятия

1.4 Связь между моделями Мили и Мура

1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов

1.6 Минимизация числа внутренних состояний автомата

Список литературы

Введение

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

Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.

1. Абстрактные цифровые автоматы

1.1 Основные понятия

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

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

Общая теория автоматов подразделяется на абстрактную и структурную.

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

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

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

Абстрактный ЦА определяется множеством, состоящим из шести элементов:

X={x 1 , x 2 ,. x n } - множество входных сигналов (входной алфавит);

Y={y 1 , y 2 , y m } - множество выходных сигналов (выходной алфавит);

А={ a 0 ,a 1 , a 2 ,. а N } - множество состояний (алфавит состояний);

а о - начальное состояние (а о

- функция выходов автомата, задающая либо отображение (XxA)

Иными словами, функция переходов

Функция выходов показывает, что автомат S, находясь в некотором состоянии а j

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

Абстрактный автомат функционирует в дискретном автоматном времени t=0,1,2,. и переходы из состояния в состояние осуществляются мгновенно. В каждый момент tдискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии а о. В момент времени t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал х (t)

1.2 Типы абстрактных автоматов

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

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

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

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

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

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) =

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

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

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

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

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

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,

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