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

Многофункциональные детерминированные абстрактные автоматы 3-го рода используются не только для реализации функций однозначного перехода в новое состояние а(t) при

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

Контрольная работа

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией


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

1. Некоторые понятия в теории абстрактных автоматов

В литературе по классическим автоматам [12–14; 18–19; 21; 24; 26; 32; 90; 125; 140] даны некоторые важные понятия о взаимоотношениях между автоматами, такие, как: эквивалентность между автоматами, изоморфизм абстрактных автоматов, взаимоотношения между автоматами первого (Мили) и второго (Мура) рода.

Рассмотрим эти понятия.

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

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

При взаимоотношениях между автоматами первого и второго рода Глушковым было доказано, что автомат второго рода можно свести к автомату первого рода, то есть интерпретировать автомат второго рода как автомат первого рода.

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

2.Табличные и графические способы задания классических автоматов Мили и Мура

Задание классического монофункционального абстрактного автомата А сводится к заданию функций переходов δ и функций выходов λ. Из соображений практики остановимся более подробно на способах задания автоматов с помощью таблиц и графов. Обычно для автоматов Мили функции переходов и выходов (2.3) задаются соответствующими таблицами с двумя входами. Столбик таблицы переходов 1 и таблицы выходов 2 обозначает состояние автомата аii Q), а строка – входной сигнал хkk Х).

Таблица 1

Таблица 2

На пересечении столбиков и строк таблицы переходов 1 ставится новое состояние автомата аs(t), в которое автомат переходит под воздействием входного сигнала хk(t) из предыдущего состояния аi(t – 1), то есть аs(t) = =δ(аi(t–1), хk(t)).

На пересечении столбиков и строк таблицы выходов 2 ставится выходной сигнал автомата уs(t), который автомат выдает под воздействием входного сигнала хk(t) и предыдущего состояния аi(t – 1), то есть уs(t) = λ(аi(t – 1), хk(t)).

Для автоматов Мура функции переходов и выходов (2.4) задаются соответствующей одной отмеченной таблицей Столбик таблицы переходов в отмеченной таблице 3 задается аналогично, как это делается в таблице переходов 1 автомата Мили. Это связано с тем, что функции переходов в автоматах Мили и Мура совпадают (см. формулы (2.3) и (2.4)). Однако, функции выходов в автоматах Мура уi(t) = λ(аi(t)), зависят только от одной переменной состояния аii Q). В связи с этим в таблице переходов добавляется строка над строкой наименования состояний аi, в которой отмечаются выходные сигналы уi, которые зависят от соответствующих аi состояний автомата.

Таблица 3

Таким образом, с помощью таблиц 1 – 3 можно полностью задать функционирование автомата Мили или Мура в автоматном дискретном времени t. В автоматном непрерывном времени у2(Т) выходной сигнал автомата Мура описывается более подробно и более точно в (2.16).

Более наглядно задается функционирование автомата Мили с помощью направленных графов, у которых состояния аi автомата отображается в кружочках (вершинах графа), а переходы из одного состояния аiв другое аk отображается стрелочкой, над которой устанавливается символ хk входного сигнала, способного перевести автомат в состояние аk. Выходные сигналы уi автомата Мили отображаются рядом с хk входными сигналами, в связи с тем, что они зависят от тех же переменных и появляются в одно и тоже автоматное время t.

Функционирование автомата Мура с помощью направленных графов, у которых состояния аi автомата отображается в кружочках (вершинах графа), а переходы из одного состояния аiв другое аk отображается стрелочкой, над которой устанавливается символ хk входного сигнала, способного перевести автомат в состояние аk. Выходные сигналы уk автомата Мура отображаются рядом с состояниями аk, в которые перешел автомат. Это связано с тем, что уk выходной сигнал появляется на выходном узле после перехода автомата в новое аk состояние, о чем говорит сдвинутая функция выходов автомата Мура.

Рис. 1. Направленный граф автомата Мили

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

Задание многофункциональных абстрактных автоматов 1-го, 2-го и 3-го рода сводится к заданию соответствующих однозначной функций переходов δo,функций выходов λ1, λ2, λ3, функцией сохранения состояний δe и функции укрупненных переходов δy. Остановимся более подробно на способах задания автоматов с помощью таблиц и графов.

Описание работы многофункционального автомата первого рода задается множествами (не менее двух) таблиц переходов, множествами таблиц выходов и таблицей сохранения состояний. Проиллюстрируем задание многофункционального автомата А1первого рода в таблицах 4 – 8.

Строки в таблицах 4 – 8 соответствуют входным сигналам хi, а столбцы – блокам π1 состояний, сохраняющих еj входных сигналов. Обычно крайний столбец в таблицах обозначен начальным состоянием а0.

На пересечении строк и столбцов таблиц однозначных переходов ставится состояние а(t)= (а(∆-1), х(t)), в котором автомат 1-го рода переходить из состояния а(∆-1) под воздействием информационного х(t) входного сигнала в состояние а(t) в тактовый момент t автоматного непрерывного времени Т. В таблицах выходов автомата 1-го рода – соответствующий переходу выходной сигнал у(t)= λ1(а(∆-1), х(t)) типа 1.

Таблица 4

Таблица 5

Таблица 6

Таблица 7

Строки таблицы сохранения состояний (табл. 8) соответствуют сохраняющим е(∆) входным сигналам, а столбцы – а(∆) состояниям автомата. В каждой строке на пересечении со столбцами в таблице сохранения состояний ставится соответствующее состояние а(∆)=δе(а(t), е(∆)), где а πj, а(t) = =а(∆) (πj Q), сохраняемое под воздействием сохраняющего е(∆) входного сигнала во время внутреннего такта ∆ автоматного непрерывного времениТ, а в остальных случаях ставятся прочерки.

Таблица 8

При описании работы многофункционального автомата А 2-го рода выходной сигнал зависит только от запоминаемых состояний блока πj автомата, которые устанавливаются в тактовый момент t и сохраняются во время реализации функций сохранения состояний во время внутреннего такта ∆ автоматного непрерывного времени Т.

Автоматы 1-го и 2-го рода способны осуществлять функции переходов в тактовый момент t автоматного непрерывного времени Т под воздействием информационных х(t) входных сигналов.

Работа автомата 2-го рода может быть задана с помощью отмеченных таблиц функций δoоднозначных переходов вместе с функцией λ2 таблицы выходов типа 2 и таблицы сохранения состояний (табл. 8). Пример табличного описания автомата 2-го рода А3 приведен в таблицах 8 –10.

Автоматы 3-го рода качественно отличаются от автоматов 1-го и 2-го рода тем, что они способны осуществлять переходы из одного состояния в другое не только в тактовый момент t под воздействием информационных х(t) входных сигналов, но и во время внутреннего такта ∆ под воздействием сохраняющих е(∆) входных сигналов автоматного непрерывного времени Т. Это принципиальное отличие автоматов 3-го рода позволяет им осуществлять переходы в матричной структуре схем автоматной памяти (МФСП), которые происходят не только в блоках πj состояний в тактовый момент t, представляющих строку состояний МФСП , но и в блоках μi во время внутреннего такта ∆, представляющих столбец состояний МФСП, за один внешний тактТ автоматного непрерывного времени.

Таблица 9

Таблица 10

Автоматы 1-го, 2-го и 3-го рода также отличаются своими функциями λ1, λ2 и λ3 выходных сигналов, рассматриваемых в автоматном непрерывном времени Т.

Функция выходов λ1 автоматов 1-го рода реализуется только в тактовый момент t под воздействием информационных х(t) входных сигналов и состояний автомата а(∆-1), то есть у(t)= λ1(а(∆-1), х(t)), где у YI.

Функция выходов λ2 автоматов 2-го рода реализуется в тактовый момент t после перехода автомата в новое состояний под воздействием информационных х(t) входных сигналов и предыдущего во времени состояния автомата а(∆-1). Функция выходов λ2, во первых, является по этому сдвинутой по сравнения с началом тактового момента t, а также зависит только от вновь установленного состояния а(t) и сохраняемого состояния а(∆), где а(t) = а(∆) и у(Т) = λ2(а(t), а(∆)), где у YII.

Функция выходов λ3 автоматов 3-го рода реализуется во время внутреннего тактового момент ∆ в новое состояний под воздействием сохраняющих е(∆) входных сигналов и состояний автомата а(∆). Функция выходов λ3,во первых, является сдвинутой

Похожие работы

1 2 3 4 5 > >>