Абстрактная теория автоматов - Коммуникации, связь, цифровые приборы и радиоэлектроника контрольная работа

Основные понятия абстрактных детерминированных автоматов Мили и Мура, как монофункциональных так и многофункциональных, реализуемых на триггерах. Понятия многофункциональных детерминированных автоматов 1-го, 2-го и 3-го рода на схемах автоматной памяти.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1. Понятие об абстрактном автомате
Объектом изучения в абстрактной теории автоматов с точки зрения системного подхода вплоть до 90-х годов ХХ столетия являлись абстрактные автоматы Мили и Мура, функционирующие в дискретном автоматном времени. В последующие годы, в связи с бурным развитием больших интегральных схем и сверхбольших интегральных схем (СБИС), которые представляют собою целые функциональные блоки компьютера (процессоры, оперативную память и т. д.), интерес к теории автоматов упал, хотя все они реализуются автоматами Мили и Мура. Даже некоторыми учеными в конце ХХ века высказывалась мысль, что теория автоматов себя изжила.
Однако, это совсем не так! Лучшим подтверждением является создание теории многофункциональных автоматов (в том числе и автоматов Мараховского), которые дали толчок для развития новых направлений в таких областях вычислительной техники, как:
1. теории построения схем автоматной памяти, которая в состоянии изменять свои состояния по двум переменным с реконфигурацией структуры запоминания состояний;
2. теории построения многоуровневых схем памяти, которые в состоянии обрабатывать одновременно общую информацию (в автомате стратегии) и частную информацию (в схемах автоматной памяти) без предварительной обработки;
3. методов построения компьютера на предложенных схемах памяти, способных реконфигурировать структуру обработки информации и одновременно обрабатывать частную и общую информацию без предварительной обработки;
Кроме этого, данные автоматы способны осуществлять переход по двум входным переменным, а также реализовать как вероятностные, так и нечеткие переходы, которые, по мнению авторов, найдут свои применения в области реконфигурируемых вычислительных устройств и систем.
Рассмотрим понятия об абстрактных автоматах Мили, Мура и Мараховского.
2 . Понятие об абстрактных автоматах Мили и Мура
В теории абстрактных автоматов часто отвлекаются от его структуры. Понятие абстрактного автомата в теории дискретных устройств воплотило в себе системный подход, при котором предмет или явление рассматриваются как нечто целостное, и основной акцент в исследованиях делается на выявлении многообразии связей и отношений с внешней средой. Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании систем, выходы которых зависят не только от состояния входов в данный момент, но и от некоторой предыстории, то есть от сигналов, которые поступали на входы системы ранее и изменяли ее функционирование. Состояния, рассматриваемые в данный момент, и соответствуют некоторой памяти о прошлом, позволяя устранять время как явную переменную и выразить выходной сигнал как функцию только с аргументами состояния и входного сигнала в данный отрезок времени.
С точки зрения последовательных монофункциональных автоматов Мили и Мура общая характеристика автомата достаточно полно описана в работе [26], в которой комбинационные схемы названы формерами . Известны канонические схемы автоматов Мили, Мура или в общем случае С- автомата. Эти автоматы представляет собой устройства из взаимодействующих регистра на триггерах и комбинационных схем [26],
В частном случае автомат может состоять из одной комбинационной схемы и тогда его рассматривают как автомат с одним состоянием или тривиального автомата, либо из одного регистра, запоминающего не менее двух состояний, и тогда его рассматривают как нетривиальный автомат Мура с памятью.
Класс автоматов, у которых выход не зависит от предыстории, и в каждый момент времени определяется лишь входным сигналом в этот же момент времени, называется комбинационными схемами, которые в своей структуре не имеют обратных цепей для запоминания, как это осуществляется в схемах памяти. Такой класс автоматов на абстрактном уровне можно описать трехкомпонентным вектором:
Ш Х - конечное множество входных сигналов ;
Ш Y - конечное множество выходных сигналов ;
Ш л : Х > Y - функция выходов, реализующая отображение ц л Х на Y.
Комбинационные схемы иногда называют функциональными преобразователями и изображают следующим образом (рис. 1):
Определение 1. Абстрактный автомат А Мили или Мура задается как совокупность шести объектов:
· Х - конечное множество входных сигналов, называемых входным алфавитом;
· Y - конечное множество выходных сигналов, называемых выходным алфавитом;
· Q - произвольное множество, называемое множеством состояний автомата;
· а 0 - элемент из множества Q, называемым начальным состоянием автомата;
· двух функций д ( а, х ) и л ( а, х ), задающих однозначные отображения множества пар ( а, х ), где а Q и х Х, в множества Q и Х.
Функция д( а, х) называется функцией перехода автомата, а функция л ( а, х ) - функцией выходов (для автомата Мили) или сдвинутой л ( а ) функцией выходов (для автомата Мура). Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов, - автоматом второго рода.
Абстрактный автомат Мили или Мура функционирует в дискретном времени, принимая целые неотрицательные значения t = 0, 1, 2, … . В каждый момент времени t этого времени он находится в определенном состоянии а ( t) из множества Q состояний автомата, причем в начальный момент времени t= 0 автомат всегда находится в своем начальном состоянии а 0 , то есть а (0) = а 0 . В каждый момент времени t , отличный от начального, автомат способен воспринимать входной сигнал х ( t ) - произвольную букву входного алфавита Х и выдавать соответствующий выходной сигнал у ( t ) - некоторую букву выходного алфавита Y .
Процедура, устанавливающая соответствие между последовательностями входных, состояний и выходных сигналов, называют функционированием модели абстрактного автомата.
Автомат с начальным состоянием а 0 называют инициальным абстрактным конечным автоматом.
Закон функционирования абстрактного автомата в случае автомата первого рода (автомата Мили) задается уравнениями в автоматном дискретном времени:
а ( t ) = д ( а ( t - 1) , х ( t )), у 1 ( t ) = л 1 ( а ( t - 1) , х ( t )), ( t = 1, …), (3)
для автомата второго рода (автомата Мура), функционирующего в автоматном дискретном времени, - уравнениями:
а ( t ) = д ( а ( t - 1) , х ( t )), у 2 ( t ) = л 2 ( а ( t )), ( t = 1, …),(4),
а в случае С -автомата, в котором реализовались функции выходов автоматов Мили и Мура - уравнениями:
а ( t ) = д ( а ( t - 1) , х ( t )), у 1 ( t ) = л 1 ( а ( t - 1) , х ( t )), у 2 ( t ) = л 2 ( а ( t )),
Установлением закона функционирования заканчивается определение абстрактного автомата. Смысл понятия абстрактного автомата состоит в реализации некоторого отображения ц множества слов входного алфавита в множество слов выходного алфавита. Отображение ц в автоматах Мили и Мура реализуется так: каждое слово входного алфавита Х = ( х 1 , х 2 , …, х n ), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А , установленного предварительно в начальное состояние а 0 . Возникающая таким образом конечная последовательность входных сигналов , автомата А , на основании закона функционирования автомата вызывает появление однозначно определенной конечной последовательности q= y (1), y (2), …, y ( k ) выходных сигналов. Эту последовательность называют выходным словом , соответствующим входному слову р . Допустимыми входными словами называются те и только те входные слова р , на которых с помощью функций д и л (описанным выше способом) определяются соответствующие выходные слова q=ц ( р ).
Рис. 2 Структурные схемы монофункциональных автоматов 1-го и 2-го рода
Построенное указанным способом искомое отображение ц , а именно: q = =ц ( р ), называют отображением , индуцированным абстрактным автоматом А .
Автомат называется конечным , если конечны все три определяющие его множества Х, Y, Q . Автомат называется вполне определенным , если его функции переходов д и выходов л заданы на всех парах ( а, х ), и частичным автоматом - в противном случае.
По количеству выполняемых преобразований все множество автоматов делится на два класса: монофункциональные автоматы Мили и Мура и многофункциональные автоматы Мили и Мура.
Каноническая схема автомата Мили (рис. 2, а ), автомата Мура (рис. 2, б ) или С- автомата в обобщенном виде (рис. 2, в ) состоят из, связанных между собою, регистра и комбинационных схем.
Монофункциональный автомат имеет жесткую структуру и всегда реализует одно и то же преобразование { X } в { Y }. Для такого автомата величина функциональности f равна 1 ( f = 1).
3. Понятие об многофункциональных абстрактных автоматах Мили и Мура
С конца 60-х и начала 70-х годов ХХ века начались исследования последовательных многофункциональных логических устройств [32; 90-91; 138; 143]. Эти работы положили начало общей теории многофункциональных автоматов Мили и Мура. В этих работах использовались триггеры с коммутируемыми функциями входных и выходных сигналов, управляемые автоматами стратегии (настройки). Вначале в автоматах стратегии обрабатывалась общая информация, которая потом своими выходными сигналами настраивала многофункциональный автомат на реализацию одного монофункционального автомата Мили, Мура или С -автомата, в которых обрабатывалась частная информация.
Основа многофункциональных автоматов Мили и Мура была положена в структуры реконфигурируемых устройств компьютерной техники, в их алгоритмическое управление и в программное обеспечение искусственного интеллекта [16; 23; 25; 30; 33; 39; 41-42; 47; 52; 88; 91; 98; 102; 109-112; 116; 124; 132-134; 142].
В общем случае автомат может характеризоваться не одной парой функций д и л , а несколькими такими функциями. Тогда он реализует при каждой i -ой настройке различные отображения ц i (не менее двух) автомата, которые определяются парой функций переходов д ( i ) и выходов л ( i ) .
Определение Абстрактный многофункциональный автомат А Мили или Мура задается как совокупность восьми объектов:
А = ( Х, Y, Q, Д, Л, Q 0, U , f ),(6)
· Х - конечное множество входных сигналов, называемых входным алфавитом;
· Y - конечное множество выходных сигналов, называемых выходным алфавитом;
· Q - произвольное множество, называемое множеством состояний автомата;
· Q 0 - множество из множества Q, называемым начальным множеством состояний автомата ( Q 0 Q );
· Д - множество функций переходов д ( i ) ( а, х ) и л( а, х ), задающих однозначные отображения множества пар ( а, х ), где а Q и х Х, в множества Q и Х ;
· Л - множество функций выходов л ( i ) ( а, х ), задающих однозначные отображения множества пар ( а, х ), где а Q и х Х, в множества Q и Х ;
· U - множество настроек функций переходов и выходов ( U= { U д , U л });
· f - функциональность автомата, которая описывается как: .
Некоторый i- й монофункциональный автомат А і задается как шестикомпонентный кортеж или вектор:
А і = ( Х і , Y і , Q і , д (і) , л (і) , а (і) 0 ),(7)
в котором компоненты автомата не отличаются от компонентов, описанных в (2)
Исходя из уравнений (3) и (4) функционирования монофункциональных автоматов 1-го и 2-го рода, получим уравнения законов функционирования детерминированных многофункциональных абстрактных автоматов таких же типов 1-го и 2-го рода:
Для многофункциональных автоматов 1-го рода (автоматов Мили) задается уравнениями в автоматном дискретном времени:
а (і) ( t ) = д (і) ( а (і) ( t - 1) , х (і) ( t ), U (і) д ),
у (і) ( t ) = л (і) ( а (і) ( t - 1) , х (і) ( t ), U (і) л ), (8)
для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, - уравнениями:
а (і) ( t ) = д (і) ( а (і) ( t - 1) , х (і) ( t ), U (і) д ),
у (і) ( t ) = л (і) ( а (і) ( t ), U (і) л ), (9),
а, в случае, объединенного С -автомата, в котором реализуются функции выходов автоматов Мили и Мура - уравнениями:
а (і) ( t ) = д (і) ( а (і) ( t - 1) , х (і) ( t ), U (і) д ),
у 1 (і) ( t ) = л (і) ( а (і) ( t - 1) , х (і) ( t ), U (і) л ),
у (і) ( t ) = л (і) ( а (і) ( t ), U (і) л ), (10)
Смысл понятия многофункционального абстрактного автомата состоит в реализации некоторого множества отображений ц i множества слов входного i- го алфавита в множество слов выходного i- го алфавита. Отображение ц i в автоматах Мили и Мура реализуется так: каждое слово входного i- го алфавита Х i = ( х 1 , х 2 , …, х n ), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А i из множества многофункционального автомата А , установленного предварительно в начальное состояние а (i) 0 . Возникающая таким образом конечная последовательность р i входных сигналов , автомата А i , на основании закона функционирования автомата вызывает появление однозначно определенной i- й конечной последовательности q i = y (1), y (2), …, y ( k ) выходных сигналов. Эту последовательность q i называют выходным i-м словом , соответствующим входному слову р i . Допустимыми входными словами называются те, и только те, входные слова р i , на которых с помощью функций д (і) и л (і) (описанным выше способом) определяются соответствующие выходные слова q i = ц( р i ).
Каноническая схема многофункционального абстрактного автомата с настройкой функций переходов и выходов представлена на рис. 3.
Монофункциональные и многофункциональные автоматы 1-го и 2-го рода и их объединение С- автомат [21; 24-26; 32; 90], реализующие свою регистровую память на триггерах и функционирование которых рассматривается в автоматном дискретном времени, являются частным случаем автоматов Мараховского (многофункциональных автоматов 1-го и 2-го рода) [55].
Автоматы Мараховского реализуют свою регистровую память на схемах автоматной памяти, и функционирование их рассматривается в автоматном непрерывном времени.
4. Некоторые понятия об изменениях в функционировании и самоорганизации в автоматах
При решении различных задач теории автоматов часто возникают дополнительные условия на рассматриваемые автоматы, определяющие те или иные подклассы класса всех конечных автоматов [59; 93]. Одним из таких условий является понятие многофункциональных автоматов совместно с автоматами настройки (автоматами стратегии).
При проникновении в структуру процессов самоизменения и самоорганизации делается целесообразным рассмотрение не отдельного автомата (алгоритмов), а системы автоматов (алгоритмов). В простейшем случае такая система состоит из двух автоматов (алгоритмов). Первый из этих двух является многофункциональным и называется рабочим автоматом (алгоритмом) и осуществляет непосредственную переработку подаваемой на его вход частной информации. Второй может быть монофункциональным или тоже многофункциональным автоматом (алгоритмом). Он предназначенный для обработки общей информации, оценки функционирования рабочего автомата (алгоритма), внесения соответствующих изменений в функционирование рабочего автомата и называется контролирующим или обучающим , а иногда и автоматом стратегии . В случае, когда рассматриваются автоматы Мили и Мура, то эти изменения вносятся в функции переходов и выходов рабочего автомата (рис. 4).
Если контролирующий автомат первой ступени многофункциональный, то под ним можно поместить контролирующий автомат второй ступени, в задачу которого входит оценивать действия автомата первой ступени и вносить в него необходимые изменения. По аналогии можно вводить контролирующие автоматы третьей, четвертой и даже более высокой ступени. Построенную подобным образом иерархию автоматов (алгоритмов) называют многоступенчатой или системой автоматов , применительно к понятиям самоизменения, самоорганизации и самосовершенствования. Подобная многоступенчатая организация системы самосовершенствующихся автоматов (алгоритмов) позволяет моделировать высокие формы самосовершенствования и самоорганизации [25].
При рассмотрении теории самоорганизующих систем (автоматов, алгоритмов) весьма существенным являются понятия одномерной и многомерной случайной величины, значениями которых являются конечные упорядоченные наборы вещественных чисел или, иначе говоря, вещественные векторы той или иной (конечной) размерности.
Различают непрерывные и дискретные случайные величины. Непрерывная случайная величина может принимать произвольные значения в той или иной области (открытом множестве) соответствующего векторного пространства. Совокупность возможных значений дискретной случайной величины могут служить лишь дискретные множества точек, каждая точка которого может быть заключена в сферу, не содержащую других точек того же самого множества. Свойство случайности, рассматриваемых величин, распространяется и при испытаниях . В каждом испытании случайная величина принимает значение из области ее определения.
Области определения дискретных случайных величин могут быть конечными либо счетными бесконечными. В обоих случаях выполняется условие нормировки:
где суммирование предполагается распространенным на всю область определения данной случайной величины.
5. Некоторые модификации абстрактных конечных автоматов
Содержательная модель абстрактного конечного автомата основывается на ряде предположений относительно работы исследуемого реального устройства. Обобщая некоторые из этих предположений, получаем различные модификации понятия абстрактного автомата: асинхронного , вероятностного , нечеткого и т. д.
Работа реального устройства, которое исследуется в моделях автоматов Мили и Мура, наблюдается лишь в выделенные моменты времени t 1 , t 2 , и т.д. Изменения, происходящие с устройством, между наблюдаемыми моментами с точностью до несущественных деталей определяются информацией в моменты t 1 , t 2 и т.д. Одно из возможных обобщений этого допущения заключается в рассмотрении двух независимых последовательностей времени t 1 , t 2 и ф 1 , ф 2 , таких, что в моменты t 1 , t 2 наблюдаются поступающие на входные узлы внешние сигналы, а в моменты ф 1 , ф 2 - наблюдаются выходные сигналы устройства. При этом предполагается, что устройство имеет функцию перехода. Эта функция однозначно определяется по входному сигналу и состоянию устройства и описывается уравнением (3) во времена t 1 , t 2 , …. Выходные сигналы устройства определяются во времени ф 1 , ф 2 , …, которые определятся соотношениями: t n ? ф s < ф s +1 < …< ф s+l < t n+ 1 , и однозначно определяются по входному сигналу и состоянию устройства в момент времени t n .
Возникающая в результате модель представляет собою содержательную модель абстрактного конечного асинхронного автомата.
Абстрактный конечный асинхронный автомат определяется как автоматы Мили и Мура, но без начального состояния. Асинхронные автоматы реализуют преобразования слов из входного алфавита Х* в выходной алфавит Y* , при котором длина слова может изменяться, а также быть пустой. В частности, асинхронный автомат может заменять каждый символ а ( i ) слова p = а (1), а (2)… а ( m ) на кодирующий этот символ слово в алфавите Y* и выполнять ряд других преобразований слов, встречающихся в теории кодирования.
Успехи развития теории алгоритмов и теории детерминированных автоматов поставили на повестку дня задачу выявления новых принципиальных возможностей, которые таит в себе использование случайных актов в процессе дискретной обработки информации. Смысл теории вероятностных автоматов состоит в получении позитивного значения случайности в дискретных преобразователях информации. Вероятностный автомат по существу появляется только тогда, когда вероятности не постулируются вычислимыми. Вероятностный автомат определен как неконструктивный элемент из-за предположения об отсутствии вычислимости вероятностных переходов, кроме специального случая, когда рассматривается рациональный вероятностный автомат [18].
Рассматривается еще одна модификация конечного автомата - нечеткие автоматы . Теория нечетких подмножеств наилучшим образом позволяет структурировать все то, что разделено не очень точными границами, например, мысль, язык, восприятия людей. Заслуга профессора Л.А. Заде состоит во введении понятия взвешенной принадлежности, которая дает понятие нечеткого (размытого) подмножества [34-35].
Нечеткие автоматы получаются в результате замены функций переходов и выходов нечеткими отношениями. Нечеткое подмножество М задается функцией, отображающейся в отрезке [0, 1]. Таким образом, роль функции переходов и выходов в нечетком автомате осуществляют функции, отображающие множества Q Ч X Ч Q и Q Ч X Ч Y в отрезке [0, 1], где Q - множество состояний , X - входной алфавит , Y - выходной алфавит . Для нечетких автоматов естественно обобщаются основные понятия и задачи, характерные для нечетких автоматов [34-35; 55; 64].
Вероятностные и нечеткие автоматы в этой монографии подробно рассматриваться не будут. Это связано тем, что они обычно на практике не применяются в виде конструктивных элементов.
Однако, на взгляд авторов это не совсем верное утверждение.
Математика предлагает куда более простое объяснение. В 1928 году Фрэнк Пламптон Рамсей, английский математик, философ и экономист, доказал, что такие упорядоченные конфигурации неизбежно присутствуют в любой большой структуре, будь то группа звёзд, совокупность случайно разбросанных камешков или последовательность чисел, полученных бросанием игральной кости. Если речь идёт о достаточно большом количестве звёзд, то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию: прямую линию, прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактически теория Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру. Как впервые провозгласил около четверти века назад американский математик Теодор С. Моцкин, из теории Рамсея следует, что полный беспорядок невозможен [144].
6. Понятие об абстрактных многофункциональных автоматах Мараховского
Функционирование абстрактных многофункциональных автоматов Мараховского, построенных на схемах автоматной памяти [64], рассматривается в автоматное непрерывное время (рис. 1.3).
Для лучшего понимания использования автоматного непрерывного времени рассмотрим в нем работу последовательных монофункциональных автоматов Мили и Мура.
Определение 3. Монофункциональный абстрактный автомат, включающий в виде компонентов пустое слово е и функцию д е сохранения состояний, описывается восьмикомпонентным вектором:
А = ( Х , Y , Q , д , л, д е , a 0 , e ), (12)
Ш компоненты Х , Y , Q , д , л и a 0 имеют те же значения и тот же смысл, что и при описании вектора (2);
Ш е ( е Х ) - сохраняющий входной сигнал;
Ш д е : Q е > Q - функция сохранения состояния, реализующее отображение на Q , при котором произвольное состояние a і ( a і Q ) сохраняет свое значение.
Пустое слово е (?), названное сохраняющим входным сигналом , воздействует в автомате А на его входные узлы во время отсутствия входных сигналов х ( t ), где х Х. При одновременном воздействии входных сигналов х ( t ) и е ( t ) сигнал е ( t ) поглощается сигналом х ( t ):
Структуру восьмикомпонентного монофункционального абстрактного автомата А в обобщенном виде представлена на рис. 5.
В реальных устройствах на входные узлы поступает последовательная пара входных сигналов х ( t ) и е (?), которые определяют элементарное входное слово р ( Т ) = х ( t ) , е (?). При использовании в качестве схем памяти триггеров, все состояния элементов памяти запоминаются только при одном сохраняющем е (?) входном сигнале. Этот сохраняющий е (?) входной сигнал не в состоянии изменить состояние автомата. Это и объясняет то, что в автоматах, в которых используются в качестве памяти триггеры, входной сигнал е (?) опускается, а функционирование самого абстрактного автомата рассматривается в автоматное дискретное время.
Однако, на уровне абстрактной теории автоматов Мараховского, которые в дальнейшем будем просто называть автоматом М, с многофункциональной системой организации памяти, используют переходы по двум переменным х ( t ) и е (?) в схемах автоматной памяти [61-63], значение сохраняющего е (?) входного сигнала необходимо учитывать и использовать для рассмотрения функционирования автоматов в автоматном непрерывном времени [55; 64].
Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою подмножества µ i состояний автомата, а строки - подмножества р j состояний автомата (табл. 1).
Таблица 1. Матрица состояний схемы автоматной памяти
Триггеры и многостабильные схемы памяти (МСП) можно представить как строку р 0 автоматной матрице (табл. 1) в связи с тем, что все ее a i состояния сохраняются при одном сохраняющем е (?) входном сигнале в одном множестве всех его состояний. Эти схемы обладают полнотой функций переходов, когда из каждого a k состояния можно под воздействием определенного входного х ( t ) сигнала перейти в любое, наперед заданное, a i состояние схемы памяти; а также полнотой системы выходов, когда каждое a i состояние отождествляется с выходным у i сигналом, который отличный от всех других.
В многофункциональной схеме автоматной памяти (МФСП) [63] переходы в момент t под воздействием входных х ( t ) сигналов могут происходить из одного состояния в другое в определенном подмножестве р i , а в моменты ? автоматного непрерывного времени Т под воздействием входного е (?) сигнала могут происходить переходы из одного состояния в другое в определенном подмножестве µ i состояний автомата. Таким образом, в матричной схеме автоматной памяти возможны переходы по двум переменным х ( t ) и е (?) в одном машинном такте Т автоматного непрерывного времени [64].
Определение 4. Математическою моделью дискретного устройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный автомат М определяемый как пятнадцатикомпонентный кортеж или вектор [64]:
А = ( Х, Е, Y I , Y II , Y III , Q , р, e 0 , a 0 , д o , д e , д y , л 1 , л 2 , л 3 ), (14)
· Х = { x 0 , x 1 ,…, x N-1 } - множество информационных входных сигналов (входной информационный алфавит);
· Е = { е 0 , е 0 ,…, е R-1 } - множество сохраняющих входных сигналов (входной сохраняющий алфавит);
· Y I = {} - множество выходных сигналов типа 1 (выходной алфавит типа 1):
· Y II = {} - множество выходных сигналов типа 2 (выходной алфавит типа 2);
· Y III = {} - множество выходных сигналов типа 3 (выходной алфавит типа 3);
· Q = { a 0 , a 1 ,…, a m 1 } - произвольное множество состояний (алфавит состояний);
· р = { р 0 , р 1 ,…, р R-1 } -множество блоков р j состояний (алфавит блоков состояний);
· е 0 Е - начальный сохраняющий входной сигнал;
· a 0 р 0 - начальное состояние автомата;
· д o : Q X> Q - однозначная функция переходов, реализующая отображение в Q. Другими словами, функция д o : некоторым парам „состояние - информационный входной сигнал” ( а (?-1), х ( t )) ставит в соответствие состояние автомата а ( t )= д o ( а (?-1), х ( t )), где а Q ;
· д e : функция сохранения состояний блока р j при а р j , реализующая отображение в р j . Другими словами, функция д е : некоторым парам „состояние - сохраняющий входной сигнал” ( а ( t ), е (?)) ставит в соответствие состояние автомата а (?)= д е ( а ( t ), е (?)), где а р j , а ( t ) = а (?) ( р j Q );
· д y : Q E> р j - функция укрупненных переходов, реализующая отображение в р j . Другими словами, функция д у некоторым парам „состояние - сохраняющий входной сигнал” ( а ( t ), е (?)) ставит в соответствие состояние автомата а (?)= д у ( а ( t ), е (?)), где а ( t ) р p , а (?) р j , а ( t ) а (?) ( а ( t ) , а (?) Q) ;
· л 1 : Q X> Y I - функция выходов типа 1, реализующая отображение в Y I . Другими словами, функция л 1 : некоторым парам „состояние - информационный входной сигнал” ( а (?-1), х ( t )) ставит в соответствие выходной сигнал автомата у ( t )= л 1 ( а (?-1), х ( t )), где у Y I ;
· л 2 : Q > Y II - функция выходов типа 2, реализующая отображение в Y II . Другими словами, функция л 2 : некоторым парам „состояние - состояние” ( а ( t ), а (?)), которые равны друг другу а ( t )= а (?), ставит в соответствие выходной сигнал автомата у ( Т )= л 2 ( а ( t ), а (?)), где у Y II ;
· л 3 : Q E> Y III - функция выходов типа 3, реализующая отображение в Y III . Другими словами, функция л 3 : некоторым парам „состояние - сохраняющий входной сигнал” ( а (?), е (?)) ставит в соответствие выходной сигнал автомата у (?)= л 3 ( а (?), е (?)), где у Y III ;
Абстрактные автоматы М представляют собою объединение автоматов 1-го, 2-го и 3-го рода, функционируют в автоматное непрерывное время Т i , которое состоит из двух отрезков t i и ? i ( Т i = t i + ? i ), описанных ранее.
В каждый момент ? i автомат способен воспринимать входной е (?) сохраняющий сигнал - произвольную букву входного сохраняющего алфавита Е и находится в определенном состоянии а( ?) подмножества р j из множества Q ( р j Q ) состояний автомата, причем в начальный момент времени ?=0 инициальный автомат всегда находится в своем начальном состоянии а 0 , то есть а (0)= а 0 .
В каждый момент t i автомат 1-го рода способен воспринимать входной х ( t ) информационный сигнал - произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а ( t ), которое принадлежит определенному подмножеству состояний р j , сохраняющегося при входном сигнале е j (?) и входящего во множество состояний Q ( р j Q ), а также выдавать соответствующий выходной сигнал у 1 ( t ) - некоторую букву выходного алфавита Y I .
Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 1-го рода задается уравнениями:
В каждый момент t i автомат 2-го рода способен воспринимать входной х ( t ) информационный сигнал - произвольн
Абстрактная теория автоматов контрольная работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Туған Жерім Қазақстан Эссе
Дипломная работа по теме Виды многополосной продукции, их преимущества и недостатки
Практические Методы В Исследовательской Работе
Реферат: Изготовление заготовки сердцевины одномодового оптического волокна
Сочинение Про Осеннюю Погоду 6 Класс
Сочинение Библиотека Будущего 3 Класс
Дипломная работа по теме Современное правовое государство: понятие, принципы и перспективы развития
Проблема Чтения Сочинение По Бакланову Аргументы
Реферат Сообщение О Пермский Губернатор
Контрольная Работа На Тему Культура Эпохи Возрождения (Ренессанса)
Реферат: Анализ среды СП "Санта-Бремор" ООО
Реферат Воинские Символы
Контрольная работа: Расчет количественных характеристик надежности
Курсовая Работа На Тему Конструкция Экипажной Части Тепловоза
Дипломная работа по теме Природные ресурсы - как основа функционирования мировой экономики
Пособие по беременности и родам. Условия назначения, размер пособия, период выплаты.
Курсовая работа по теме Сущность основных требований, предъявляемых к методике урока, к деятельности и подготовке педагога
Реферат По Теме Описание И Создание Блога
Реферат: Українська жіноча проза кінця ХХ століття: світоглядні моделі й особливості художнього стилю
Методы Диагностики Кариеса Реферат
Человек – феномен природы - Биология и естествознание реферат
Плазуни. Особливості будови та життєдіяльності - Биология и естествознание презентация
Проходка горных выработок - Геология, гидрология и геодезия курсовая работа