Понятие о конечных автоматах

Содержание

Слайд 2

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

Термин «конечный автомат» используется для обозначения одного класса

1 Способы задания конечных автоматов Термин «конечный автомат» используется для обозначения одного
цифровых устройств, находящих применение в автоматике, телемеханике, вычислительной технике.
В отличие от комбинационных схем эти устройства содержат память. Выходные сигналы конечного автомата (КА) зависят от значений на входах не только в данный момент времени, но и от предыдущих значений входных сигналов.
Необходимая информация о сигналах, поступивших на входы раньше, может быть учтена посредством введения промежуточных сигналов, которые связаны с внутренней структурой автомата и называются состояниями автомата.

Слайд 3

Используют два типа моделей КА – абстрактная и структурная.
Абстрактный автомат –

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

Слайд 4

Если на вход АА подавать буква за буквой некоторую последовательность букв входного

Если на вход АА подавать буква за буквой некоторую последовательность букв входного
алфавита х1, х2, х3... – входное слово, то на выходе АА будут последовательно появляться буквы выходного алфавита у1, у2, у3… – выходное слово.
АА может быть задан:
1 Аналитическим способом
2 Табличным или матричным способом
3 Графическим способом

Слайд 5

При аналитическом способе задания АА задается множеством из пяти элементов:
A =

При аналитическом способе задания АА задается множеством из пяти элементов: A =
{X, Y, Q, Гq, q1}
где Х = {х1, х2,..., хn} – множество входных сигналов (входной алфавит);
Y={y1, y2,...,ym} – множество выходных сигналов (выходной алфавит);
Q={q1, q2,…,qr} – множество возможных внутренних состояний (алфавит состояний);
Гq = { Гq1, Гq2,..., Гqr} – отображение множества Q в себя, которое любому и каждой входной букве
сопоставляет состояние определяющее функцию переходов , и выходную букву , определяющую
функцию выходов

Слайд 6


Пусть
Х = {х1,х2,х3}- входные сигналы,
Y={y1,у2,y3,y4,y5,у6}- выходные сигналы,

Пусть Х = {х1,х2,х3}- входные сигналы, Y={y1,у2,y3,y4,y5,у6}- выходные сигналы, Q = {q1,q2,q3,q4,q5}-

Q = {q1,q2,q3,q4,q5}- состояния автомата
Закон отображения имеет вид
Гq1 = {q2(x1/y1), q4(x2/y3), q5(x3/y4)},
Гq2 = {q3(x1/y6), q1(x2/y1)},
Гq3 = {q1(x2/y5), q4(x3/y3)},
Гq4 = {q4(x1/y4), q5(x2/y2)},
Гq5 = {q1(x1/y5), q2(x3/y1)}.
АА переходит из состояния q1 в состояние q2, если на входе х1, при этом на выходе появляется y1; АА переходит из состояния q1 в q4, если на входе x2, при этом на выходе появляется у3; АА переходит из состояния q1 в q5, если на входе х3, при этом на выходе появляется у4.

Слайд 7

Автомат называется конечным, если конечны множества X, Y, Q.
Функция переходов φ(q, x)

Автомат называется конечным, если конечны множества X, Y, Q. Функция переходов φ(q,
и функция выходов ψ(q, x) определяют закон функционирования конечного автомата в дискретные моменты времени.
На практике наибольшее распространение получили автоматы Мили и Мура.
Закон функционирования автомата Мили задается уравнениями
которые показывают, что q(t+l) и y(t) однозначно определяются состоянием q(t) и входным сигналом x(t).

Слайд 8

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

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

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

Слайд 9

Если функции φ и ψ определены на всех значениях q(t) и x(t),

Если функции φ и ψ определены на всех значениях q(t) и x(t),
то такие автоматы называются полными или полностью определенными.
Если функции φ и ψ определены не на всех значениях q(t) и x(t), то такие автоматы называются частичным.
Табличный способ предполагает задание АА с помощью обобщенной таблицы переходов и выходов.
Строки таблицы соответствуют возможным значениям входного сигнала, а столбцы – внутренним состояниям автомата.
На пересечении строки и столбца указывается очередное состояние автомата и через косую черту соответствующее значение выходного сигнала.

Слайд 10

Так автомату А, заданному ранее аналитическим способом, соответствует таблица.

Автомат является частичным.

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

Слайд 11

АА можно задать также матрицей соединений автомата.
Строки и столбцы этой матрицы

АА можно задать также матрицей соединений автомата. Строки и столбцы этой матрицы
соответствуют различным состояниям автомата.
На пересечении qk–строки и ql–столбца записывается буква входного алфавита, вызывающая переход автомата из состояния qk в ql, а через косую черту – буква выходного алфавита которая появляется на выходе автомата.
Если ни одна из букв входного алфавита не переводит автомат из состояния qk в ql, то на соответствующем пересечении ставится нуль.

Слайд 12

Матрица соединений автомата имеет вид

Матрица соединений автомата имеет вид

Слайд 13

При графическом способе задания АА изображается в виде ориентированного графа.
Вершины графа

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

Слайд 14

При описании КА различают также понятие структурного автомата.
В отличие от АА,

При описании КА различают также понятие структурного автомата. В отличие от АА,
имеющего один вход и один выход, структурный автомат (СА) имеет р входов (u1, u2, ..., uР) и ℓ выходов (v1,v2,...,ve), на каждом из которых сигнал может принимать два значения – 0 или 1.
Таким образом, букве хi входного алфавита АА соответствует вектор, компонентами которого являются нули и единицы – сигналы на входах СА.

Слайд 15

Для кодирования входных сигналов АА различными векторами должно быть выполнено условие
р выбирается

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

Слайд 16

2 Синтез конечных автоматов

Используемый на практике метод синтеза КА предполагает, что общая

2 Синтез конечных автоматов Используемый на практике метод синтеза КА предполагает, что
структура автомата имеет вид

Слайд 17

Первое комбинационное устройство (КУ1) вырабатывает входные сигналы (сигналы возбуждения) для элементов памяти

Первое комбинационное устройство (КУ1) вырабатывает входные сигналы (сигналы возбуждения) для элементов памяти
(ЭП).
Второе комбинационное устройство (КУ2) вырабатывает выходные сигналы автомата.
Синтез КА сводится к определению количества элементов памяти и выбору их типов, а также к построению схем КУ1 и КУ2 в выбранном базисе.
В качестве ЭП, обеспечивающих временную задержку сигналов на один такт, используются серийно выпускаемые триггеры.

Слайд 18

Триггер – это двоичный запоминающий элемент, имеющий один или несколько входов и

Триггер – это двоичный запоминающий элемент, имеющий один или несколько входов и
два выхода.
Под действием входных сигналов триггер может переключаться в любое из двух устойчивых состояний (0 или 1) и сохранять это состояние в течение заданного времени.
Так как триггеры имеют только два устойчивых состояния, их называют элементарными автоматами. Выходные сигналы триггера совпадают с его состоянием.
Описать работу триггера можно таблицей переходов, в которой указываются значения 0 или 1 входных сигналов, вызывающих один из четырех возможных типов переходов:
0→0; 0→1; 1→0; 1→1.

Слайд 19

Рассмотрим несколько типов триггеров.
D-триггер. Функциональная схема D-триггера приведена на рисунке
Триггер имеет один

Рассмотрим несколько типов триггеров. D-триггер. Функциональная схема D-триггера приведена на рисунке Триггер
вход D и два выхода w и
Таблица определяет переходы D-триггера w(t) →w(t+1).

Слайд 20

Название D-триггера произошло от английского слова Delay (задержка), так как его следующее

Название D-триггера произошло от английского слова Delay (задержка), так как его следующее
состояние равно сигналу на входе D, задержанному на один такт.
2. Т-триггер или триггер со счетным входом.

При T=0 триггер находится в состоянии хранения информации, сигнал T=1 вызывает переключение триггера в противоположное состояние.

Слайд 21

3. RS-триггер. Сигнал S (от англ. set – установка) переключает триггер в

3. RS-триггер. Сигнал S (от англ. set – установка) переключает триггер в
единичное состояние, а сигнал R (англ. reset – переустановка) вызывает переключение триггера в нулевое состояние.
Вход S называется единичным установочным, а вход R – нулевым установочным.

Слайд 22

Символ * означает, что подача сигналов ноль или единица на соответствующие входы

Символ * означает, что подача сигналов ноль или единица на соответствующие входы
S и R не влияет на данный переход триггера.

Слайд 23

4. J-K триггер. Вход J называется единичным установочным входом, а вход К

4. J-K триггер. Вход J называется единичным установочным входом, а вход К
– нулевым установочным.
В J-K триггере допускается одновременная подача входных сигналов J = l и К = 1.

Слайд 24

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

Структурный синтез автоматов заключается в составлении системы логических

3 Способы задания конечных автоматов Структурный синтез автоматов заключается в составлении системы
функций, на основании которой строятся комбинационные устройства, формирующие выходные сигналы и сигналы возбуждения элементов памяти (триггеров).
Выделяют пять основных этапов структурного синтеза.
1. Кодирование входного и выходного алфавитов АА, кодирование состояний АА. Чтобы закодировать входные сигналы АА, нужно каждой букве входного алфавита поставить в соответствие совокупность значений двоичных сигналов u1,u2,…, uP на входах СА. При этом количество р физических входов СА определяют из условия выбирая ближайшее целое число.

Слайд 25

При кодировании выходных сигналов АА каждой букве yj (j=1,…,m) выходного алфавита ставится

При кодировании выходных сигналов АА каждой букве yj (j=1,…,m) выходного алфавита ставится
в соответствие совокупность значений двоичных сигналов v1,v2,...,ve на выходах СА.
Количество е физических выходов СА определяют из условия
Каждой букве qk (k=1,…,r) алфавита состояний абстрактного автомата ставится в соответствие совокупность значений двоичных сигналов w1,w2,...,wZ состояний (выходов) элементов памяти. Количество элементов памяти определяют из условия
выбирая ближайшее целое число.

Слайд 26

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

Принцип кодирования переменных будет определять сложность схем комбинационных устройств, формирующих сигналы возбуждения
Di (i = 1,2,3) триггеров и выходные сигналы Vj (j = 1, 2, 3).
Минимальное число слагаемых в ДСНФ для Di и Vj получается при следующем алгоритме кодирования:
1) Упорядочить кодируемые переменные в порядке уменьшения числа их появлений в таблице переходов-выходов;
2) Первая из них, т. е. наиболее часто встречающаяся, кодируется нулевым кодом, затем используются коды, содержащие по одной единице, затем по две и т. д., до тех пор, пока все состояния не будут закодированы.

Слайд 27

2. Выбор типа элементарных автоматов (элементов памяти).
При выборе элементов памяти ориентируются

2. Выбор типа элементарных автоматов (элементов памяти). При выборе элементов памяти ориентируются
на имеющуюся элементную базу. Для выбранного типа триггеров составляют таблицу переходов, в которой для каждого возможного типа переходов указана комбинация сигналов на входах (сигналов возбуждения триггеров).
3.Составление обобщенной таблицы переходов и выходов для закодированных переменных.
4.Определение функций возбуждения элементарных автоматов и выходных функций СА. Минимизация этих функций.
5. Составление структурной схемы синтезируемого автомата, т. е. составление комбинационной схемы, реализующей функции возбуждения ЭА и выходные функции СА.

Слайд 28

4 Пример

Осуществить структурный синтез АА, заданного обобщенной таблицей переходов и выходов.
В

4 Пример Осуществить структурный синтез АА, заданного обобщенной таблицей переходов и выходов.
качестве элементов памяти использовать D-триггеры, в качестве элементной базы использовать логические элементы И, ИЛИ, НЕ.

Слайд 29

В соответствии с таблицей, количество букв входного алфавита АА п=3, количество букв

В соответствии с таблицей, количество букв входного алфавита АА п=3, количество букв
выходного алфавита m = 6, количество состояний r = 5.
Определим количество входов СА:

принимаем р = 2

принимаем е = 3.

принимаем z = 3.

Закодируем переменные xj, vj, qk.

Слайд 30

1

1

1

3

3

2

2

1

3

1

2

2

2

1

1 1 1 3 3 2 2 1 3 1 2 2 2 1

Слайд 31

На основании результатов кодирования строим обобщенную таблицу переходов и выходов СА ,

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

Слайд 32

Составим обобщенную таблицу функционирования СА

Составим обобщенную таблицу функционирования СА

Слайд 33

По таблице запишем СДНФ выходных функций V1, V2 и V3 и функций

По таблице запишем СДНФ выходных функций V1, V2 и V3 и функций
возбуждения триггеров D1, D2 и D3, зависящих от набора переменных u1, u2, w1(t), w2(t), w3(t).
В результате получим систему логических функций для построения комбинационной части автомата:

Слайд 34

Осуществить минимизацию функций Vi , Dj.

Осуществить минимизацию функций Vi , Dj.

Слайд 35

Карта Карно для функции V2

Карта Карно для функции V2

Слайд 36

Карта Карно для функции V3

Карта Карно для функции V3

Слайд 37

Карат Карно для функции D1

Карат Карно для функции D1

Слайд 38

Карат Карно для функции D2

Карат Карно для функции D2

Слайд 39

Карат Карно для функции D3

Карат Карно для функции D3

Слайд 40

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

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

Слайд 41

Дешифратор должен обеспечить переход от кодов выходного алфавита к самим буквам.
Таблица

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


;


;

Имя файла: Понятие-о-конечных-автоматах-.pptx
Количество просмотров: 152
Количество скачиваний: 3