Лекция Конечные автоматы. Автоматы мура и Мили



бет1/2
Дата22.10.2019
өлшемі82.87 Kb.
түріЛекция
  1   2
Лекция 8. Конечные автоматы. Автоматы мура и Мили
Теория автоматов представляет собой раздел дискретной математики, изучающий модели, преобразователи дискретной информации. Такими преобразователями являются как реальные устройства: компьютеры, живые организмы; так и воображаемые устройства: аксиоматические теории, математические машины.

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

Автомат функционирует в абстрактном времени. Все переходы происходят мгновенно.

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

Абстрактный автомат (АА) – дискретный преобразователь информации; представляет собой множество, состоящее из шести элементов:

S = {A, X, Y, , }

где


A{a1,…,am} – множество внутренних состояний,

X {x1,…,xn} – множество входных сигналов (входной алфавит),

Y {y1,…,yf} – множество выходных сигналов (выходной алфавит),

 – функция переходов автомата из одного состояния в другое:

 – функция выхода,

- начальное состояние автомата.



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

Рисунок 1. Представление абстрактного автомата


На рисунке 1: t – дискретное время: t = nT, где T – интервал (такт), разделяющий дискретные моменты времени; если T = 1, то t = n, т. е. дискретное время сопоставляется упорядоченному ряду натуральных чисел.

Абстрактный автомат (АА) можно рассматривать как "черный ящик" с одним входом и одним выходом, с которым можно экспериментировать, не зная, что находится внутри.



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

Рисунок 2. Преобразование входных слов в выходные


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

На практике широкое распространение получили две основные модели, описывающие функционирование АА:

1. Модель Мили;

2. Модель Мура.


Законы функционирования автоматов

В зависимости от законов функционирования различают автоматы:

1. Автоматы первого рода, или автоматы Мили:

a(t+1)=  (a(t),x(t))

y(t)=(a(t),x(t))

t – текущий момент времени; t+1 – следующий момент времени; а(t+1) – состояние автомата в следующий момент времени; a(t), x(t), y(t) – элементы описания автомата в текущий момент времени.

2. Правильные автоматы второго рода, или автоматы Мура:

a(t+1)= (a(t),x(t))

y(t)=(a(t))

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


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

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

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

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, , } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов  и выходов . При этом среди множества A = {a0,a1,…, an} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

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

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

Таблица переходов (ТП)


xj\aj

a0



an

x1

(a0,x1)



( an,x1)









xm

( a0,xm)



( an,xm)



Таблица выходов (ТВ)

xj\aj

a0



an

x1

(a0,x1)



( an,x1)









xm

( a0,xm)



( an,xm)

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = [ ai,xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = [ ai,xj].



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

xj\ai

a0



an

x1

(a0,x1)/ (a0,x1)



(an,x1)/ (an,x1)









xm

(a0,xm)/ (a0,xm)



(an,xm)/ (an,xm)



Пример 1: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).

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

δ

a1

a2

a3

X1

a1

a3

a1

X2

a2

a1

a2




Таблица выходов

λ

a1

a2

a3

X1

y2

y2

y2

X2

y1

y1

y2




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

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

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


yg

(a0)



(an)

xj\ac

a0



an

x1

(a0,x1)



(an,x1)









xm

(a0,xm)



(an,xm)

Автомат Мили




xj\ai

a0

a1

a2

a3

x1

a1/y1

a2/y3

А3/y2

a0/y1

x2

a0/y2

a0/y1

A3/y1

a2/y3

Автомат Мура



yg

y2

y1

y1

y3

y2

xj\xj

a0

a1

a2

a3

a4

x1

a2

a1

a3

a4

a2

x2

a3

a4

a4

a0

a1

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

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

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

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

x1x2x2x2x1… x1x2x2x2x1

a0a1a0a0a0a1 a0a2a4a1a4

y1y1y2y2y1 y2y1y2y1y2



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

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



а) б)





Достарыңызбен бөлісу:
  1   2




©dereksiz.org 2020
әкімшілігінің қараңыз

    Басты бет