Без темы
<<  ОБРАЗОВАТЕЛЬНЫЙ ПРОЕКТ как цикл инновационной деятельности Общая часть  >>
Модуль 3. Общая теория конечные цифровых автоматов с памятью
Модуль 3. Общая теория конечные цифровых автоматов с памятью
Абстрактный автомат
Абстрактный автомат
Абстрактный автомат (продолжение)
Абстрактный автомат (продолжение)
Способы задания автоматов: а) табличный
Способы задания автоматов: а) табличный
Способы задания автоматов: б) графический
Способы задания автоматов: б) графический
Синхронные и асинхронные автоматы
Синхронные и асинхронные автоматы
Связь между моделями Мура и Мили
Связь между моделями Мура и Мили
Преобразование автомата Мура в автомат Мили и наоборот
Преобразование автомата Мура в автомат Мили и наоборот
Преобразование автомата Мили в автомат Мура (продолжение)
Преобразование автомата Мили в автомат Мура (продолжение)
Результат преобразований
Результат преобразований
Минимизация полностью определённых автоматов
Минимизация полностью определённых автоматов
Нахождение классов эквивалентных состояний методом Ауфенкампа и Хона
Нахождение классов эквивалентных состояний методом Ауфенкампа и Хона
ПРИМЕР: минимизация автомата Мили
ПРИМЕР: минимизация автомата Мили
Постановка задачи структурного синтеза автоматов
Постановка задачи структурного синтеза автоматов
Постановка задачи структурного синтеза автоматов (продолжение)
Постановка задачи структурного синтеза автоматов (продолжение)
Контрольные вопросы
Контрольные вопросы

Презентация: «Общая теория конечные цифровых автоматов с памятью». Автор: Афанасьев В А. Файл: «Общая теория конечные цифровых автоматов с памятью.pptx». Размер zip-архива: 186 КБ.

Общая теория конечные цифровых автоматов с памятью

содержание презентации «Общая теория конечные цифровых автоматов с памятью.pptx»
СлайдТекст
1 Модуль 3. Общая теория конечные цифровых автоматов с памятью

Модуль 3. Общая теория конечные цифровых автоматов с памятью

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

Теория автоматов. Модуль 3

1/16

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

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

Основные понятия и определения

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

Абстрактный автомат – это математическая модель, с одним входом и одним выходом, работающая в дискретном времени tn = nT, где n = 0, 1, 2 …, а T – интервал дискретизации.

Предполагается, что переходные процессы в автомате укладываются в интервал дискретизации и, поэтому чтобы не ссылаться на значение Т, вводится автоматное время: t= tn / T = 0, 1, 2, …

В каждый момент времени t автомат, находящийся в состоянии а(t) Є А, способен воспринять букву входного алфавита z(t) Є Z и, в этот же момент времени, сформировать букву выходного алфавита w(t) Є W (t = 0, 1, 2, …). Например: t 0 1 2 3 z(t) z1 z2 z3 z4 w(t) w1 w2 w3 w4

Теория автоматов. Модуль 3

2/16

3 Абстрактный автомат (продолжение)

Абстрактный автомат (продолжение)

Автомат Мили (G. Mealy) as = ?(am , zf ) wl = ? (am , zf )

Автомат Мура (E. Moore) as = ?(am , zf ) wl = ? (am )

Теория автоматов. Модуль 3

3/16

Работу автомата можно определить следующими двумя функциями: a(t+1)=?(a(t), z(t)) – функция перехода, w(t)= ?(a(t), z(t)) – функция выхода. Примем: a(t)=am - состояние для момента времени t, a(t+1)= as - состояние для момента t+1. Аналогично: z(t)=zf , w(t)=wl . Тогда: as = ?(am ,zf ) – функция перехода, wl = ? (am ,zf ) - функция выхода.

Введем ряд понятий: Автомат будет конечным, если все множества A, W и Z будут конечными. Детерминированный автомат – такой автомат, который, находясь в состоянии am под воздействием входного сигнала zf перейдет в состояния as . Инициальный автомат: а(0)=а1 . Полностью определенный автомат – если для каждой пары (am , zf ) Є {A x Z} определены функции ? и ?. Если это не выполняется – автомат будет неполным или частичным.

Из всех автоматов наибольшее распространение получили автоматы Мили и Мура

4 Способы задания автоматов: а) табличный

Способы задания автоматов: а) табличный

t

0

1

2

3

4

Z\а

a1

a2

a3

z(t)

z1

z1

z2

z1

z1

a3/w1

a1/w1

a1/w2

w(t)

w1

w2

w1

w1

z2

a1/w1

a3/w2

a2/w1

a(t)

a1

a3

a1

a1

a3

Ниже представлена совмещённая таблица переходов и выходов автомата Мили А1, в клетках которой на пересечении m- го столбца (состояние am) и f-й строки (вх. символ zf) указываются состояние автомата as = ?(am ,zf) в следующий момент времени t+1 и значение выходного символа (через косую линию) wl = ? (am ,zf ) в этот же момент времени t.

Ниже, основываясь на таблице переходов и выходов, определено выходное слово автомата как реакция на произвольное входное слово. Выходной сигнал wl в автомате Мили присутствует только при наличии входного сигнала zf !

Выходное слово автомата

Мили А1

Теория автоматов. Модуль 3

4/16

5 Способы задания автоматов: б) графический

Способы задания автоматов: б) графический

Z\а

a1

a2

a3

Z\а

Z\а

w1

w2

w1

w1

w2

a1

a2

a3

a4

a5

z1

a3/w1

a1/w1

a1/w2

z1

a4

a4

a1

a2

a2

z2

a1/w1

a3/w2

a2/w1

z2

a1

a2

a5

a3

a3

Мили А1

Мура А2

Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними.

Теория автоматов. Модуль 3

5/16

Таблица переходов и выходов автомата Мура отличается тем, что у него выходной сигнал есть функция только состояния wl = ? (am ). Ниже приведён пример таблицы автомата Мура А2

6 Синхронные и асинхронные автоматы

Синхронные и асинхронные автоматы

Предварительно определим, какое состояние автомата является устойчивым. Состояние автомата as является устойчивым, если для любого входа zf Є Z такого, что as=?(am ,zf ) справедливо as= ?(as ,zf ), т. е. если автомат в состояние as пришёл под действием входного сигнала zf , то выйти из него он должен под действием другого сигнала.

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

Если хотя бы одно состояние автомата является неустойчивым, то такой автомат будет синхронным. Приведённые примеры автоматов Мили А1 и Мура А2 являются синхронными. В дальнейшим, как правило, будет рассматриваться данный тип автомата.

Теория автоматов. Модуль 3

6/16

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

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

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

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

7/16

Два автомата А1 и А2 называются эквивалентными (независимо от модели автоматов), если будучи установленными в начальное состояние а1 имеют одинаковые реакции (выходные слова) на любое входного слово. Выходным сигналом автомата Мура (в отличие от автомата Мили) находящегося в начальном состоянии пренебрегают.

Покажем, что автоматы Мили А1 и Мура А2 являются эквивалентными. При определении эквивалентности «разномодельных» автоматов необходимо учитывать факт сдвига на один такт (запаздывание) выходного слова автомата Мура относительно выходного слова автомата Мили.

Z\а

Z\а

w1

w2

w1

w1

w2

Z\а

a1

a2

a3

a1

a2

a3

a4

a5

z1

a3/w1

a1/w1

a1/w2

z1

a4

a4

a1

a2

a2

z2

a1/w1

a3/w2

a2/w1

z2

a1

a2

a5

a3

a3

Реакции автоматов, установленных в состояние а1 на входное слово ? = z1 z1 z2 z1 z2 z2

Мили А1

Мили А1

Мили А1

?

z1

z1

z2

z1

z2

z2

a(t)

a1

a3

a1

a1

a3

a2

a3

w(t)

w1

w2

w1

w1

w1

w2

Мура А2

Мура А2

a(t)

a1

a4

a2

a1

a4

a3

a5

w(t)

w1

w1

w2

w1

w1

w1

w2

8 Преобразование автомата Мура в автомат Мили и наоборот

Преобразование автомата Мура в автомат Мили и наоборот

Мили А3

Теория автоматов. Модуль 3

8/16

1. Преобразование автомата Мура в автомат Мили (Мура А2 ? Мили А3) осуществляется наиболее просто. Правило преобразования применительно к интерпретации автоматов в виде графов: выходной сигнал wl, записанный в вершине as переносится на все дуги, входящие в эту вершину.

Правило преобразования применительно к заданию автоматов в виде таблиц: в клетки таблицы, отражающие состояния переходов as= ?(as , zf ) автомата Мура записываются (через косую черту) соответствующие этим состояниям выходные сигналы. Т.О. новый автомат Мили приобретает число состояний автомата Мура.

2. Преобразование автомата Мили в автомат Мура (Мили А1 ? Мура А4). Всевозможные состояния эквивалентного автомата Мура определятся множеством всех пар (as,wl) автомата Мили, где wl – выходной сигнал, приписанный к входящей в as дуге . Пары объединяют в группы, включающие одинаковые состояния as . Состояния эквивалентного автомата Мура будем обозначать как bs .

Z\а

a1

a2

a3

a4

a5

z1

a4/ w1

a4/ w1

a1/w1

a2/ w2

a2/w2

z2

a1 /w1

a2/w2

a5/ w2

a3/w1

a3/ w1

9 Преобразование автомата Мили в автомат Мура (продолжение)

Преобразование автомата Мили в автомат Мура (продолжение)

Z\а

Z\а

w1

w2

w1

w1

w2

Z\а

a1

a2

a3

b1

b2

b3

b4

b5

z1

a3/w1

a1/w1

a1/w2

z1

b4

b4

b1

b2

b2

z2

a1/w1

a3/w2

a2/w1

z2

b1

b1

b5

b3

b3

Состояние a1 автомата Мили А1 порождает 2 состояния автомата Мура А4, которые обозначим b1 и b2 .

Далее запишем группы состояний автомата Мура А4 для состояний a2 и a3 автомата Мили А1:

(Мили А1 -> Мура А4)

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

9/16

В дальнейшем символы bi можно заменить на ai. В качестве начального состояния автомата Мура A4 можно выбрать любое из состояний, порождённых начальным состоянием a1 в автомате Мили A1.

10 Результат преобразований

Результат преобразований

Z\а

a1

a2

a3

Z\а

Z\а

w1

w2

w1

w1

w2

a1

a2

a3

a4

a5

z1

a3/w1

a1/w1

a1/w2

z1

a4

a4

a1

a2

a2

z2

a1/w1

a3/w2

a2/w1

z2

a1

a2

a5

a3

a3

Z\а

a1

a2

a3

a4

a5

Z\а

Z\а

w1

w2

w1

w1

w2

z1

a4/ w1

a4/ w1

a1/w1

a2/ w2

a2/w2

b1

b2

b3

b4

b5

z1

b4

b4

b1

b2

b2

z2

a1 /w1

a2/w2

a5/ w2

a3/w1

a3// w1

z2

b1

b1

b5

b3

b3

Вследствие свойства транзитивности отношений эквивалентности (теория множеств) имеем: Мура A4 эквивавалентен Мили A3.

Теория автоматов. Модуль 3

10/16

11 Минимизация полностью определённых автоматов

Минимизация полностью определённых автоматов

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

Избыточность состояний автомата устраняется склеиванием эквивалентных между собой состояний. Состояния am и as считаются эквивалентными, если автомат находящийся в любом из них, формирует одинаковые выходные слова при подаче на его вход произвольных входных слов или последовательностей символов. Объединение всех эквивалентных друг другу состояний образует класс эквивалентных состояний. Если всё множество состояний автомата разбить на классы эквивалентных состояний с последующей заменой каждого класса одним состоянием, то будет получен автомат с минимальным числом состояний.

Теория автоматов. Модуль 3

11/16

12 Нахождение классов эквивалентных состояний методом Ауфенкампа и Хона

Нахождение классов эквивалентных состояний методом Ауфенкампа и Хона

Делается это за ряд шагов, руководствуясь при этом более слабым отношением (определением) эквивалентности, а именно, принципом k- эквивалентных состояний. Будем называть k- эквивалентными два состояния автомата Мили (am и as , k=1,2,3, ..), если автомат находясь в любом из них, при подаче на его вход слов из k- букв выдаёт на выходе одинаковые слова, т. е. (am? as), если ?(am, ?k )=?(as, ?k ) для входных слов ?k длиной k. Объединение всех k- эквивалентных состояний образуют класс k- эквивалентных состояний. Например, 1- эквивалентных состояний автомата Мили включает состояния с одинаковыми выходными сигналами в таблице переходов и выходов. Доказано, что если результаты разбиения состояний автомата на классы k и k+1- эквивалентности совпали, то классы k-эквивалентных состояний являются эквивалентными в строгом смысле этого понятия.

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

12/16

13 ПРИМЕР: минимизация автомата Мили

ПРИМЕР: минимизация автомата Мили

zi\ai

a1

a2

a3

a4

a5

a6

z1

a2/w2

a5/w1

a2/w1

a5/w1

a2/w1

a5/w2

z2

a1/w2

a2/w2

a5/w2

a3/w2

a5/w2

a6/w2

z3

a6/w1

a6/w1

a4/w2

a5/w2

a6/w1

a1/w1

zi\ai

zi\ai

b1

b1

b2

b2

b3

b3

a1

a6

a2

a5

a3

a4

z1

b2

b2

b2

b2

b2

b2

Дальнейшее разбиение бессмысленно. Пусть: (a1, a6 )=a1, (a2, a5 )=a2, (a3 )=a3, (a4 )= a4. Окончательный вид таблицы переходов автомата Мили приобретёт следующий вид.

z2

b1

b1

b2

b2

b2

b3

z3

b1

b1

b1

b1

b3

b2

zi\ai

zi\ai

zi\ai

b1

b1

b2

b2

b3

b3

zi\ai

a1

a2

a3

a4

С1

С1

С2

С2

С3

c4

a1

a6

a2

a5

a3

a4

z1

a2 / w2

a2 / w1

a2 / w1

a2 / w1

z1

С2

С2

С2

С2

С2

С2

z2

a1 / w2

a2 / w2

a2 / w2

a3 / w2

z2

С1

С1

С2

С2

С2

С3

z3

a1 / w1

a1 / w1

a4 / w2

a2 / w2

z3

С1

С1

С1

С1

С4

С2

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

13/16

Обозначим классы 1 -эквивалентных состояний как ?1, тогда: ?1={(a1, a6), (a2, a5), (a3, a4)} = {b1, b2, b3}. Преобразуем исходную таблицу автомата Мили заменив в ней состояние as классами 1-эквивалентных состояний ?1.

?2={(a1, a6), (a2, a5), a3, a4}={c1 , c2 , c3 , c4 }. ?3={(a1, a6), (a2, a5), a3, a4}. ?2 = ?3!

14 Постановка задачи структурного синтеза автоматов

Постановка задачи структурного синтеза автоматов

Z

x1

x2

xK

W

y1

y2

yN

A

Q1

Q2

QR

a1

0

0

0

z1

0

0

0

w1

0

0

0

a2

0

0

1

z2

0

0

1

w2

0

0

1

aM

1

1

1

zF

1

1

1

wL

1

1

1

Теория автоматов. Модуль 3

14/16

Цель структурного синтеза – разработка схемы автомата из логических элементов заданного типа, которая функционирования бы в соответствии с таблицей переходов и выходов исходного абстрактного автомата. Представление символов первичного алфавита абстрактного автомата (из множеств Z и W) в форме удобной для передачи по линии связи называется кодированием. Для перехода от абстрактного автомата к структурному прежде всего необходимо осуществить двоичное кодирование символов используемых алфавитов, а также состояний автомата двоичными элементами памяти. Z={z1,…zf ,.., zF }; W={w1,…wl ,.., wL }; A={а1,…аm ,.., aM };

F=1 K=0, F=2 K=1, F=3 K=2, F=4 K=3 F=5 K=3, F=7 K=3, F=8 K=3, F=9 K=4 ……………. F=16 K=4.

Двоичное кодирование определит следующие количественные соотношения между мощностями первичных алфавитов и соответствующими им наборами двоичных переменных (Z?X, W ?Y, A ?Q):

15 Постановка задачи структурного синтеза автоматов (продолжение)

Постановка задачи структурного синтеза автоматов (продолжение)

zi\ai

zi\ai

w1

w2

a1

a2

z1

a1

a1

z2

a2

a2

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

15/16

На этапе структурного синтеза автомат принято представлять в виде 2-х частей – памяти и КС (КС1 и КС2). Память автомата состоит из элементарных автоматов Мура Q1 ,…,QR с двумя состояниями, обладающих полной системой переходов и выходов.

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

В структурной схеме автомата КС2 выполняет функцию выхода ?

а КС1 и память - функцию перехода ? автомата:

Где:

16 Контрольные вопросы

Контрольные вопросы

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

Какой автомат является синхронным (асинхронным)? Какие автоматы являются эквивалентными? Правило преобразования автомата Мура в эквилентный ему автомат Мили применительно к интерпретации автоматов в виде графов.

7. Каким параметром определяются количество состояний автомата Мура, полученного путём выполнения эквивалентных преобразований автомата Мили. 8. Изложите суть минимизации состояний полностью определённых абстрактных автоматов. 9. Принцип k- эквивалентных состояний Ауфенкампа и Хона. 10. Нарисуйте структурную схему структурного автомата.

Теория автоматов. Модуль 3

16/16

«Общая теория конечные цифровых автоматов с памятью»
http://900igr.net/prezentacija/ekonomika/obschaja-teorija-konechnye-tsifrovykh-avtomatov-s-pamjatju-125964.html
cсылка на страницу
Урок

Экономика

125 тем
Слайды
900igr.net > Презентации по экономике > Без темы > Общая теория конечные цифровых автоматов с памятью