Способы задания автомата (Лекция)
1. Табличный способ
2. Графический способ задания автомата
Чтобы задать конечный автомат S, необходимо описать все элементы множества S =
При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.
Строки этих таблиц соответствуют входным сигналам x ( t ), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d [ ai,xj ], в которое автомат перейдет из состояния ai под воздействием сигнала xj ; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l [ ai,xj ].
Совмещенная таблица переходов и выходов автомата Мили:
Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но и также все три алфавита: входной, выходной и алфавит состояний.
Для задания автомата Мура требуется одна таблица, поскольку в этом автомате выходной сигнал однозначно определяется состоянием автомата.
Отмеченная таблица переходов автомата Мура :
В этой таблице каждому столбцу приписан, кроме состояния ai , еще и выходной сигнал y ( t ) = l ( a ( t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.
Приведем примеры табличного задания автоматов Мили и Мура :
По этим таблицам можно найти реакцию автомата на любое входное слово. Например.
Для автомата Мили: Для автомата Мура :
2. Графический способ задания автомата (задание автомата с помощью графа)
Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as , если в автомате имеется переход из ai в as , т.е. as = d ( ai , xj ). В автомате Мили дуга отмечается входным сигналом xj , вызвавшим переход, и выходным сигналом yg , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).
Источник
Способы задания конечных автоматов
Представление конечного автомата фактически сводится к описанию задающих его автоматных функций. [8]
Существуют три способа задания конечных автоматов:
· Табличный (матрицы переходов и выходов);
· Графический (с помощью графов);
· Аналитический (с помощью формул).
Аналитический способ – автомат задаетсясистемой уравнений. Из такой системы следует, что при конечном числе возможных внутренних состояний количество возможных значений автоматных функций также оказывается конечным. Примером такого задания служат системы уравнений, задающие автоматы Мили и автоматы Мура
Табличный способ.Составляется таблица состояния автоматадля функции перехода – δ и функции выхода. При этом:
· столбцы таблицы соответствуют элементам входного алфавита X,
· строки таблицы соответствуют состояниям (элементы конечного множества Q).
Пересечению i-и строки и j-го столбца соответствует клетка (i, j), которая является аргументом функций 8 и λ автомата в момент, когда он находится в состоянии qi на его входе – слово xj, а в самой соответствующей клетке запишем значения функций 8 и λ. Таким образом, вся таблица соответствует множеству Q х X.
При заполнении таблицы переходов каждая клеточка однозначно определяется парой символов: символом следующего состояния и символом выходного сигнала.
На практике автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей перехода и матрицей выводов. При этом строки обозначаются буквами входного алфавита, а столбцы буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата).
В матрице переходов на пересечении строки xk и столбца qr помещается значение функции перехода δ(qi, х) и функции выводов λ(q, х). В ряде случаев обе таблицы объединяются в одну таблицу.
Графический способ.
Автомат задается с помощью графа, схемы, графика и др. Задание с помощью ориентированного графа – более удобная и компактная форма описания автомата.
Граф автомата содержит
· Вершины, соответствующие состоянию qiÎQ,
· Дуги, соединяющие вершины – переходы автомата из одного состояния в другое. На дугах принято указывать пары входных и выходных сигналов – сигналов переходов.
Если автомат переходит из состояния q1 в состояние q2 под воздействием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выделенными начальным и конечным состояниями.
Разработка шкалы «прибора для измерения емкости»
| № | индикация | + | — | перегруз. | выкл. | ┤ |
| 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 ; просмотров: 2775 ; Мы поможем в написании вашей работы!
Источник
Способы задания конечного автомата
Комбинационные схемы, хотя и позволяют реализовать любые фиксированные зависимости между входными и выходными сигналами, не могут изменять характера своего поведения (т.е. последовательности обработки данных) — любое такое изменение требует изменения структуры схемы, т.е., по сути, переходу к другой схеме. Решить проблему перестройки работы без изменения структуры схемы возможно, если ввести в нее элементы памяти, которые позволяли бы фиксировать и сохранять промежуточные состояния устройства — в этом случае выходной сигнал будет зависеть не только от входного сигнала, но и от состояния схемы. Если количество таких элементов конечно, то, как указывалось выше, дискретное устройство будет называться конечным автоматом.
Конечным автоматом называется система , в которой X и Y являются конечными входным и выходным алфавитами, Q — конечным множеством внутренних состояний, Y(x, q) — функцией переходов и Q(x,q) — функцией выходов.
Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) — преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если q0 — начальное состояние автомата, а i — номер такта, то его работа описывается системой:
Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с q0, последовательно находить все последующие состояния автомата и выходные символы.
Выделяются два типа автоматов — инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния q0). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества Q; этим выбором определяется дальнейшее поведение автомата.
Представление конкретного конечного автомата фактически сводится к описанию задающих его автоматных функций. Из системы (9.3) следует, что при конечном числе возможных внутренних состояний количество возможных значений автоматных функции также оказывается конечным. Их описание возможно различными способами, наиболее распространенными из которых является табличный и с помощью диаграмм.
В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы — буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (xk) и столбца (qr) помещаются значения функции Y (qr, xk), а в матрице выходов — значения функции Q(qr, xk).
Источник
Способы задания автоматов
Закон функционирования автоматов может быть задан в виде систем уравнений, таблиц, матриц и графов. Под законом функционирования понимается совокупность правил, описывающих переходы автомата в новое состояние и формирование выходных символов в соответствии с последовательностью входных символов.
В зависимости от типа автомата при табличном задании закона функционирования автомата используются либо таблицы переходов и выходов (автомат Мили), либо совмещенная таблица переходов и выходов (автомат Мура). С помощью табл. 26 и 27 (таблицы переходов и таблицы выходов соответственно) задан закон функционирования абстрактного автомата Мили, для которого
Строки таблиц отмечены входными символами (элементы множества Z), а столбцы − состояниями (элементы множества А). Входные символы и состояния, которыми помечены строки и столбцы, относятся к моменту времени t. В табл. 26 (таблице переходов) на пересечении строки zi(t) и столбца am(t) ставится состояние as(t+1)=d(am(t),zi(t)). В табл. 27 (таблице выходов) на пересечении строки zi(t) и столбца am(t) ставится выходной символ w(t)=l(am(t),zi(t)), соответствующий переходу из состояния аm в состояние as. Таким образом, по таблицам переходов и выходов можно проследить последовательность работы автомата. Так, например, в начальный момент времени t=0 автомат, находясь в состоянии a1 (первый столбец), под действием входного символа z1 может перейти в состояние a2, при этом выходной символ не формируется; под действием входного символа z2 − в состояние a4 с формированием выходного символа w2; под действием символа z3 − в состояние a3 с формированием выходного символа w3. Далее если на вход автомата, установленного в исходное состояние аm ÍA, в моменты времени t=1,2,…,n подается некоторая последовательность букв входного алфавита (входных символов) ziÍZ, то на выходе автомата будут последовательно формироваться буквы выходного алфавита (выходные символы) wjÍW, при этом автомат будет переключаться в состояния asÍA. Следовательно, с помощью таблиц переходов и выходов можно получить выходную реакцию автомата на любое входное слово.
Как отмечалось выше, для автомата Мура выходной символ не зависит от входного, а определяется только текущим состоянием автомата. Это позволяет для автомата Мура объединить обе таблицы (переходов и выходов) в одну совмещенную таблицу. В совмещенной таблице переходов и выходов каждый столбец отмечается состоянием am ÍА и выходным символом w(t)=l(a(t)), соответствующим этому состоянию.
Другим, более наглядным способом описания закона функционирования автомата является представление его в виде графа. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги − переходам между ними. Дуга, направленная из вершины am в вершину as, соответствует переходу из состояния am в as. В начале дуги записывается входной символ zi, влияющий на переход as=d(am,zi), а символ wj записывается в конце дуги (автомат Мили) или рядом с вершиной (автомат Мура). На рис. 37 приведен граф автомата Мили, соответствующий закону функционирования, описанному выше (см. табл. 26 и 27).
Источник
