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

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

Представление конечного автомата фактически сводится к описанию задающих его автоматных функций. [8]

Существуют три способа задания конечных автоматов:

· Табличный (матрицы переходов и выходов);

· Графический (с помощью графов);

· Аналитический (с помощью формул).

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

Табличный способ.Составляется таблица состояния автоматадля функции перехода – δ и функции выхода. При этом:

· столбцы таблицы соответствуют элементам входного алфавита X,

· строки таблицы соответствуют состояни­ям (элементы конечного множества Q).

Пересечению i-и строки и j-го столбца соответствует клетка (i, j), которая является аргументом функций 8 и λ автомата в момент, когда он находится в состоя­нии q_i на его входе – слово x_j, а в самой соответствующей клетке запишем значения функций 8 и λ. Таким образом, вся таблица соответствует множеству Q х X.

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

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

В матрице переходов на пересечении строки x_k и столбца q_r помещается значение функции перехода δ(q_i, х) и функции выводов λ(q, х). В ряде случаев обе таблицы объединяются в одну таблицу.

Графический способ.

Автомат задается с помощью графа, схемы, графика и др. Задание с помощью ориентированного гра­фа – более удобная и компактная форма описания автомата.

Граф автомата содержит

· Вершины, соответствующие состоянию q_iÎQ,

· Дуги, соединяющие вершины – переходы автомата из одного состояния в другое. На дугах принято указывать пары вход­ных и выходных сигналов – сигналов переходов.

Если автомат переходит из состояния q₁ в состояние q₂ под воз­действием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выде­ленными начальным и конечным состояниями.

Разработка шкалы «прибора для измерения емкости»

№	индикация	+	—	перегруз.	выкл.	┤
0	исх.сост.	1	0	0	0	нет
1	0	2	0	13	0	да
2	50	3	1	13	0	да
3	100	4	2	13	0	да
4	150	5	3	13	0	да
5	200	6	4	13	0	да
6	250	7	5	13	0	да
7	300	8	6	13	0	да
8	350	9	7	13	0	да
9	400	10	8	13	0	да
10	450	11	9	13	0	да
11	500	13	10	13	0	да
12	ОВ	0	0	0	0	нет
13	авария	0	0	0	0	нет

Рис.2.5. Граф шкалы прибора для измерения емкости

Заключение

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

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

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

Дата добавления: 2018-02-18 ; просмотров: 2765 ; Мы поможем в написании вашей работы!

Источник

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

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

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

Строки таблиц отмечены входными символами (элементы множества Z), а столбцы − состояниями (элементы множества А). Входные символы и состояния, которыми помечены строки и столбцы, относятся к моменту времени t. В табл. 26 (таблице переходов) на пересечении строки z_i(t) и столбца a_m(t) ставится состояние a_s(t+1)=d(a_m(t),z_i(t)). В табл. 27 (таблице выходов) на пересечении строки z_i(t) и столбца a_m(t) ставится выходной символ w(t)=l(a_m(t),z_i(t)), соответствующий переходу из состояния а_m в состояние a_s. Таким образом, по таблицам переходов и выходов можно проследить последовательность работы автомата. Так, например, в начальный момент времени t=0 автомат, находясь в состоянии a₁ (первый столбец), под действием входного символа z₁ может перейти в состояние a₂, при этом выходной символ не формируется; под действием входного символа z_{2 −} в состояние a₄ с формированием выходного символа w₂; под действием символа z₃ − в состояние a₃ с формированием выходного символа w₃. Далее если на вход автомата, установленного в исходное состояние а_m ÍA, в моменты времени t=1,2,…,n подается некоторая последовательность букв входного алфавита (входных символов) z_iÍZ, то на выходе автомата будут последовательно формироваться буквы выходного алфавита (выходные символы) w_jÍW, при этом автомат будет переключаться в состояния a_sÍA. Следовательно, с помощью таблиц переходов и выходов можно получить выходную реакцию автомата на любое входное слово.

Как отмечалось выше, для автомата Мура выходной символ не зависит от входного, а определяется только текущим состоянием автомата. Это позволяет для автомата Мура объединить обе таблицы (переходов и выходов) в одну совмещенную таблицу. В совмещенной таблице переходов и выходов каждый столбец отмечается состоянием a_m ÍА и выходным символом w(t)=l(a(t)), соответствующим этому состоянию.

Другим, более наглядным способом описания закона функционирования автомата является представление его в виде графа. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги − переходам между ними. Дуга, направленная из вершины a_m в вершину a_s, соответствует переходу из состояния a_m в a_s. В начале дуги записывается входной символ z_i, влияющий на переход a_s=d(a_m,z_i), а символ w_j записывается в конце дуги (автомат Мили) или рядом с вершиной (автомат Мура). На рис. 37 приведен граф автомата Мили, соответствующий закону функционирования, описанному выше (см. табл. 26 и 27).

Источник

Способы задания автомата (Лекция)

1. Табличный способ

2. Графический способ задания автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l . При этом среди множества A = 0,a₁,…, a_n > необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Строки этих таблиц соответствуют входным сигналам x ( t ), а столбцы – состояниям. На пересечении столбца a_i и строки x_j в таблице переходов ставится состояние a_s = d [ a_i,x_j ], в которое автомат перейдет из состояния a_i под воздействием сигнала x_j ; а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = l [ a_i,x_j ].

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

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

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

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

В этой таблице каждому столбцу приписан, кроме состояния a_i , еще и выходной сигнал y ( t ) = l ( a ( t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура :

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили: Для автомата Мура :

2. Графический способ задания автомата (задание автомата с помощью графа)

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a_i и a_s соединяются дугой, направленной от a_i к a_s , если в автомате имеется переход из a_i в a_s , т.е. a_s = d ( a_i , x_j ). В автомате Мили дуга отмечается входным сигналом x_j , вызвавшим переход, и выходным сигналом y_g , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

Источник

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

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

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

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

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

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

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

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

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

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

Выделяют 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 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = , где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:

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

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

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

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

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

Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:

А на схеме асинхронный RS триггер обозначается вот так:

Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.

Источник