Абстрактная теория автоматов

Размещено на http://www.allbest.ru/

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

Абстрактная теория автоматов

1. Понятие об абстрактном автомате

Объектом изучения в абстрактной теории автоматов с точки зрения системного подхода вплоть до 90-х годов ХХ столетия являлись абстрактные автоматы Мили и Мура, функционирующие в дискретном автоматном времени. В последующие годы, в связи с бурным развитием больших интегральных схем и сверхбольших интегральных схем (СБИС), которые представляют собою целые функциональные блоки компьютера (процессоры, оперативную память и т. д.), интерес к теории автоматов упал, хотя все они реализуются автоматами Мили и Мура. Даже некоторыми учеными в конце ХХ века высказывалась мысль, что теория автоматов себя изжила.

Однако, это совсем не так! Лучшим подтверждением является создание теории многофункциональных автоматов (в том числе и автоматов Мараховского), которые дали толчок для развития новых направлений в таких областях вычислительной техники, как:

1. теории построения схем автоматной памяти, которая в состоянии изменять свои состояния по двум переменным с реконфигурацией структуры запоминания состояний;

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

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

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

Рассмотрим понятия об абстрактных автоматах Мили, Мура и Мараховского.

2. Понятие об абстрактных автоматах Мили и Мура

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

С точки зрения последовательных монофункциональных автоматов Мили и Мура общая характеристика автомата достаточно полно описана в работе [26], в которой комбинационные схемы названы формерами. Известны канонические схемы автоматов Мили, Мура или в общем случае С-автомата. Эти автоматы представляет собой устройства из взаимодействующих регистра на триггерах и комбинационных схем [26],

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

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

А = (Х, Y, л),(1)

у которого:

Ш Х - конечное множество входных сигналов;

Ш Y - конечное множество выходных сигналов;

Ш л : Х > Y - функция выходов, реализующая отображение ц_л Х на Y.

Комбинационные схемы иногда называют функциональными преобразователями и изображают следующим образом (рис. 1):

Определение 1. Абстрактный автомат А Мили или Мура задается как совокупность шести объектов:

А = (Х, Y, Q, д, л, а₀),(2)

где

· Х - конечное множество входных сигналов, называемых входным алфавитом;

· Y - конечное множество выходных сигналов, называемых выходным алфавитом;

· Q - произвольное множество, называемое множеством состояний автомата;

· а₀ - элемент из множества Q, называемым начальным состоянием автомата;

· двух функций д(а, х) и л(а, х), задающих однозначные отображения множества пар (а, х), где а Q и х Х, в множества Q и Х.

Функция д(а, х) называется функцией перехода автомата, а функция л(а, х) - функцией выходов (для автомата Мили) или сдвинутой л(а) функцией выходов (для автомата Мура). Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов, - автоматом второго рода.

Абстрактный автомат Мили или Мура функционирует в дискретном времени, принимая целые неотрицательные значения t = 0, 1, 2, … . В каждый момент времени t этого времени он находится в определенном состоянии а(t) из множества Q состояний автомата, причем в начальный момент времени t=0 автомат всегда находится в своем начальном состоянии а₀, то есть а(0) = а₀. В каждый момент времени t, отличный от начального, автомат способен воспринимать входной сигнал х(t) - произвольную букву входного алфавита Х и выдавать соответствующий выходной сигнал у(t) - некоторую букву выходного алфавита Y.

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

Автомат с начальным состоянием а₀ называют инициальным абстрактным конечным автоматом.

Закон функционирования абстрактного автомата в случае автомата первого рода (автомата Мили) задается уравнениями в автоматном дискретном времени:

а(t) = д(а(t - 1), х(t)), у¹(t) = л₁(а(t - 1), х(t)), (t = 1, …), (3)

для автомата второго рода (автомата Мура), функционирующего в автоматном дискретном времени, - уравнениями:

а(t) = д(а(t - 1), х(t)), у²(t) = л₂(а(t)), (t = 1, …),(4),

а в случае С-автомата, в котором реализовались функции выходов автоматов Мили и Мура - уравнениями:

а(t) = д(а(t - 1), х(t)), у¹(t) = л₁(а(t - 1), х(t)), у²(t) = л₂(а(t)),

(t = 1, …), (5)

Установлением закона функционирования заканчивается определение абстрактного автомата. Смысл понятия абстрактного автомата состоит в реализации некоторого отображения ц множества слов входного алфавита в множество слов выходного алфавита. Отображение ц в автоматах Мили и Мура реализуется так: каждое слово входного алфавита Х = (х₁, х₂, …, х_n), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предварительно в начальное состояние а₀. Возникающая таким образом конечная последовательность входных сигналов, автомата А , на основании закона функционирования автомата вызывает появление однозначно определенной конечной последовательности 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 (не менее двух) автомата, которые определяются парой функций переходов д⁽ⁱ⁾ и выходов л⁽ⁱ⁾.

Определение Абстрактный многофункциональный автомат А Мили или Мура задается как совокупность восьми объектов:

А = (Х, Y, Q, Д, Л, Q_0, U, f),(6)

где

· Х - конечное множество входных сигналов, называемых входным алфавитом;

· Y - конечное множество выходных сигналов, называемых выходным алфавитом;

· Q - произвольное множество, называемое множеством состояний автомата;

· Q₀ - множество из множества Q, называемым начальным множеством состояний автомата (Q₀Q);

· Д - множество функций переходов д⁽ⁱ⁾(а, х) и л(а, х), задающих однозначные отображения множества пар (а, х), где а Q и хХ, в множества Q и Х;

· Л - множество функций выходов л⁽ⁱ⁾(а, х), задающих однозначные отображения множества пар (а, х), где аQ и хХ, в множества Q и Х;

· U - множество настроек функций переходов и выходов (U={U_д, U_л});

· f - функциональность автомата, которая описывается как: .

Некоторый i-й монофункциональный автомат А_і задается как шестикомпонентный кортеж или вектор:

А_і = (Х_і, Y_і, Q_і, д^(і), л^(і), а^(і)₀),(7)

в котором компоненты автомата не отличаются от компонентов, описанных в (2)

Исходя из уравнений (3) и (4) функционирования монофункциональных автоматов 1-го и 2-го рода, получим уравнения законов функционирования детерминированных многофункциональных абстрактных автоматов таких же типов 1-го и 2-го рода:

Для многофункциональных автоматов 1-го рода (автоматов Мили) задается уравнениями в автоматном дискретном времени:

а^(і)(t) = д^(і)(а^(і)(t - 1), х^(і)(t), U^(і)_д),

у^(і)(t) = л^(і)(а^(і)(t - 1), х^(і)(t), U^(і)_л), (8)

(t = 1, …, i = 1, 2, …L),

для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, - уравнениями:

а^(і)(t) = д^(і)(а^(і)(t - 1), х^(і)(t), U^(і)_д),

у^(і)(t) = л^(і)(а^(і)(t), U^(і)_л), (9),

(t = 1, …, i = 1, 2, …L),

а, в случае, объединенного С-автомата, в котором реализуются функции выходов автоматов Мили и Мура - уравнениями:

а^(і)(t) = д^(і)(а^(і)(t - 1), х^(і)(t), U^(і)_д),

у^1(і)(t) = л^(і)(а^(і)(t - 1), х^(і)(t), U^(і)_л),

у^(і)(t) = л^(і)(а^(і)(t), U^(і)_л), (10)

(t = 1, …? i = 1, 2, …L),

Смысл понятия многофункционального абстрактного автомата состоит в реализации некоторого множества отображений ц_i множества слов входного i-го алфавита в множество слов выходного i-го алфавита. Отображение ц_i в автоматах Мили и Мура реализуется так: каждое слово входного i-го алфавита Х_i = (х₁, х₂, …, х_n), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А_i из множества многофункционального автомата А, установленного предварительно в начальное состояние а⁽ⁱ⁾₀. Возникающая таким образом конечная последовательность р_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].

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



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

Области определения дискретных случайных величин могут быть конечными либо счетными бесконечными. В обоих случаях выполняется условие нормировки:

,(11)

где суммирование предполагается распространенным на всю область определения данной случайной величины.

5. Некоторые модификации абстрактных конечных автоматов

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

Работа реального устройства, которое исследуется в моделях автоматов Мили и Мура, наблюдается лишь в выделенные моменты времени t₁, t₂, и т.д. Изменения, происходящие с устройством, между наблюдаемыми моментами с точностью до несущественных деталей определяются информацией в моменты t₁, t₂ и т.д. Одно из возможных обобщений этого допущения заключается в рассмотрении двух независимых последовательностей времени t₁, t₂ и ф₁, ф₂, таких, что в моменты t₁, t₂ наблюдаются поступающие на входные узлы внешние сигналы, а в моменты ф₁, ф₂ - наблюдаются выходные сигналы устройства. При этом предполагается, что устройство имеет функцию перехода. Эта функция однозначно определяется по входному сигналу и состоянию устройства и описывается уравнением (3) во времена t₁, t₂, …. Выходные сигналы устройства определяются во времени ф₁, ф₂, …, которые определятся соотношениями: 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₀, e), (12)

у которого:

Ш компоненты Х, Y, Q, д, л и a₀ имеют те же значения и тот же смысл, что и при описании вектора (2);

Ш е (е Х) - сохраняющий входной сигнал;

Ш д_е: Q е > Q - функция сохранения состояния, реализующее отображение на Q, при котором произвольное состояние a_і(a_і Q) сохраняет свое значение.

Пустое слово е(?), названное сохраняющим входным сигналом, воздействует в автомате А на его входные узлы во время отсутствия входных сигналов х(t), где хХ. При одновременном воздействии входных сигналов х(t) и е(t) сигнал е(t) поглощается сигналом х(t):

х(t) е(t)= х(t)(13)

Структуру восьмикомпонентного монофункционального абстрактного автомата А в обобщенном виде представлена на рис. 5.

В реальных устройствах на входные узлы поступает последовательная пара входных сигналов х(t) и е(?), которые определяют элементарное входное слово р(Т) = х(t), е(?). При использовании в качестве схем памяти триггеров, все состояния элементов памяти запоминаются только при одном сохраняющем е(?) входном сигнале. Этот сохраняющий е(?) входной сигнал не в состоянии изменить состояние автомата. Это и объясняет то, что в автоматах, в которых используются в качестве памяти триггеры, входной сигнал е(?) опускается, а функционирование самого абстрактного автомата рассматривается в автоматное дискретное время.

Однако, на уровне абстрактной теории автоматов Мараховского, которые в дальнейшем будем просто называть автоматом М, с многофункциональной системой организации памяти, используют переходы по двум переменным х(t) и е(?) в схемах автоматной памяти [61-63], значение сохраняющего е(?) входного сигнала необходимо учитывать и использовать для рассмотрения функционирования автоматов в автоматном непрерывном времени [55; 64].

Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою подмножества µ_iсостояний автомата, а строки - подмножества р_j состояний автомата (табл. 1).

Таблица 1. Матрица состояний схемы автоматной памяти

	µ1	µ2	…..	µn
р0	a10	a20	…	an0
р1	a11	a21	…	an1
р2	a12	a22	…	an2
…	…	…	…	…
рm	a1m	a2m	…	anm

Триггеры и многостабильные схемы памяти (МСП) можно представить как строку р₀ автоматной матрице (табл. 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₀, a₀, д_o, д_e, д_y, л₁, л₂, л₃), (14)

у которого:

· Х = {x₀, x₁,…, x_N-1} - множество информационных входных сигналов (входной информационный алфавит);

· Е = {е₀, е₀,…, е_R-1} - множество сохраняющих входных сигналов (входной сохраняющий алфавит);

· Y_I = {} - множество выходных сигналов типа 1 (выходной алфавит типа 1):

· Y_II = {} - множество выходных сигналов типа 2 (выходной алфавит типа 2);

· Y_III = {} - множество выходных сигналов типа 3 (выходной алфавит типа 3);

· Q = {a₀, a₁,…, a_m1} - произвольное множество состояний (алфавит состояний);

· р = { р₀, р₁,…, р_R-1} -множество блоков р_j состояний (алфавит блоков состояний);

· е₀Е - начальный сохраняющий входной сигнал;

· a₀ р₀ - начальное состояние автомата;

· д_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);

· л₁: Q X> Y_I - функция выходов типа 1, реализующая отображение в Y_I. Другими словами, функция л₁: некоторым парам „состояние - информационный входной сигнал” (а(?-1), х(t)) ставит в соответствие выходной сигнал автомата у(t)= л₁(а(?-1), х(t)), где у Y_I;

· л₂: Q > Y_II - функция выходов типа 2, реализующая отображение в Y_II. Другими словами, функция л₂: некоторым парам „состояние - состояние” (а(t), а(?)), которые равны друг другу а(t)= а(?), ставит в соответствие выходной сигнал автомата у(Т)= л₂(а(t), а(?)), где у Y_II;

· л₃: Q E> Y_III - функция выходов типа 3, реализующая отображение в Y_III. Другими словами, функция л₃: некоторым парам „состояние - сохраняющий входной сигнал” (а(?), е(?)) ставит в соответствие выходной сигнал автомата у(?)= л₃(а(?), е(?)), где у Y_III;

Абстрактные автоматы М представляют собою объединение автоматов 1-го, 2-го и 3-го рода, функционируют в автоматное непрерывное время Т_i, которое состоит из двух отрезков t_i и ?_i (Т_i= t_i+?_i), описанных ранее.

В каждый момент ?_i автомат способен воспринимать входной е(?) сохраняющий сигнал - произвольную букву входного сохраняющего алфавита Е и находится в определенном состоянии а(?) подмножества р_j из множества Q (р_j Q) состояний автомата, причем в начальный момент времени ?=0 инициальный автомат всегда находится в своем начальном состоянии а₀, то есть а(0)=а₀.

В каждый момент t_i автомат 1-го рода способен воспринимать входной х(t) информационный сигнал - произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), которое принадлежит определенному подмножеству состояний р_j, сохраняющегося при входном сигнале е_j(?) и входящего во множество состояний Q (р_j Q), а также выдавать соответствующий выходной сигнал у¹(t) - некоторую букву выходного алфавита Y_I.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 1-го рода задается уравнениями:

(15)

В каждый момент t_i автомат 2-го рода способен воспринимать входной х(t) информационный сигнал - произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), которое принадлежит определенному подмножеству состояний р_j, сохраняющегося при входном сигнале е_j(?) и входящего во множество состояний Q (р_j Q), а также выдавать соответствующий выходной сигнал у²(Т) - некоторую букву выходного алфавита Y_II.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 2-го рода задается уравнениями:

(16)

В каждый момент t_i автомат 3-го рода способен воспринимать входной х(t) информационный сигнал - произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), а также способен воспринимать сохраняющийся входной сигнал е_j(?)- произвольную букву входного сохраняющего алфавита Е и осуществлять в каждый момент ?_i переход в новое состояние а(?) входящего в подмножество µ_i множество состояний Q (µ_i Q), а также выдавать соответствующий выходной сигнал у³(Д) - некоторую букву выходного алфавита Y_III.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 3-го рода задается уравнениями:

(17)

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

Смысл понятия абстрактного автомата 1-го рода состоит в реализации некоторого отображения ц₁ последовательного множества элементарных р слов, состоящих из букв входного информационного алфавита Х и букв входного сохраняющего алфавита Е, в множество слов выходного алфавита Y_I.

Каждое элементарное входное слово р (р=х, е), последовательно подается на вход данного абстрактного автомата М, установленного предварительно в начальное состояние. В момент такта t под воздействием входной х(t) буквы входного информационного алфавита Х автомат М способен перейти в новое состояние подмножества состояний р_j, сохраняющегося при входной букве е_j(?) входного сохраняющего алфавита Е автомат М, и входящего в множество состояний Q (р_j Q), а также выдавать соответствующий выходной сигнал у¹(t) - некоторую букву выходного алфавита Y_I.

Смысл понятия абстрактного автомата 2-го рода состоит в реализации некоторого отображения ц₂ последовательного множества элементарных р слов, состоящих из букв входного информационного алфавита Х и букв входного сохраняющего алфавита Е, а также выдавать соответствующий выходной сигнал у²(Т) - некоторую букву выходного алфавита Y_II.

Смысл понятия абстрактного автомата 3-го рода состоит в реализации некоторого отображения ц₃ последовательного множества элементарных р слов, состоящих из букв входного информационного алфавита Х и букв входного сохраняющего алфавита Е, в множество слов выходного алфавита Y_III.

В момент такта t под воздействием входной х(t) буквы входного информационного алфавита Х автомат М способен перейти в новое состояние а_i подмножества состояний м_i, а потом перейти в новое состояние а_k подмножества состояний м_j при входной букве е_j(?) входного сохраняющего алфавита Е автомат М, и входящего во множество состояний Q (м_i Q), а также выдавать соответствующий выходной сигнал у³(Д) - некоторую букву выходного алфавита Y_III.

Возникающие таким образом конечные последовательности входных элементарных слов р(Т) = х(t), е(?) на основании законов функционирования автомата в автоматном непрерывном времени Т вызывают соответственно определенные конечные последовательности q_i= ц_i(p) выходных букв из соответствующих входных алфавитов Y_I, Y_II, Y_III. Эту последовательность q_i называют выходным словом автомата 1-го, 2-го или 3-го рода обобщенного автомата М.

Таким образом, отнесся каждой последовательности входных элементарных слов р соответствующую ему последовательность выходного слова q_i, получаем искомое отображение ц_i, которое называют отображением, индуцированным абстрактным автоматом М, который в состоянии работать как автомат 1-го, 2-го и 3-го рода.

Абстрактный М-автомат А, который описывается вектором (14), имеет два входа Х и Е и три выхода Y₁, Y₂, Y₃ (рис. 6). Функционирование автомата исследуется в автоматном непрерывном времени Т [64; 70].

Абстрактный автомат, описывающий реальное компьютерное устройство, должен удовлетворять элементарным требованиям надежности, устойчивости состояний и выходных символов (слов). Здесь следует отступить от сугубо абстрактного понятия символов входного алфавита и учитывать, что на входные каналы (узлы) реального устройства поступают устанавливающие и сохраняющие сигналы вполне определенной длительности. Под действием какого-либо устанавливающего входного сигнала x(t) устройство переходит во вполне определенное состояние а(t) и должно оставаться в нем, пока не закончится действие этого входного сигнала. На уровне абстрактной модели это означает, что если при поступлении входного сигнала x(t) автомат перешел в состояние а(t), то он должен оставаться в нем, пока сохраняется длительность входного сигнала x(t) (многократное воздействие символа x за период времени t в состоянии а). В период воздействия сохраняющего входного сигнала e(Д) состояние а(t) сохраняется (а(t) = а(Д)) в автоматах 1-го и 2-го рода или осуществляется укрупненный переход в новое состояние а(Д), то есть состояние а(t) ? а(Д), в автоматах 3-го рода. Выполнение этого условия необходимо также для ориентации на определенную реализацию автомата в задаваемом элементном базисе [64].

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

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

7. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний

Многофункциональные автоматы на схемах автоматной памяти имеют возможность с помощью автомата настройки U выполнять комутацию функций возбуждения и выходов, как это осуществлялось при реализации в автоматах с памятью на триггерах (рис. 1.4), а также с помощью g-ступенчатого автомата А, имеющего (g-1) автомат стратегии А_М, который генерирует сохраняющие е(?) входные сигналы для абстрактного М-автомата А и выполняет перестройку (регенерацию) функций сохранения состояний многофункциональной памяти автомата А_у, что является новым в теории иерархических, многофункциональных автоматов.

Обобщенную структурную схему многофункционального автомата А на схемах автоматной памяти, которые составляют регистр R_g на схемах автоматной памяти, комбинованные схемы (КС), автомата настройки U и (g-1)-ступенчатого автомата стратегии А_М иллюстририрует рис. 8.

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

· БА (базовые автоматы типа И-НЕ, ИЛИ-НЕ или И-ИЛИ-НЕ) і-й группы управляемой МФСП А_і, количество R_i которых больше единицы (R_i>1), через сохраняющую входную шину, соединены с выходными шинами одной или нескольких МФСП А_k (k=1, 2, ..., і-1), которые составляют (g-1)-ступенчатый автомат стратегии А_М для МФСП А_і;

· устанавливающие входные и выходные шины многоуровневой схемы памяти (МУСП) А_і (і=1, 2, ..., g) соответственно соединены с общими входными и выходными шинами МУСП.

Суть принципа запоминания состояний в МУСП с много-функциональной системой организации между МФСП состоит в том, что устанавливающими входными сигналами x_i(t) состояния управляемых МФСП а_і запоминаются только в том случае, если они принадлежат блокам р_і состояний, которые запоминаются под влиянием сохраняющегося входного сигнала e_j(Д), который генерируется управляющей МФСП А_k.

Под воздействием входного сигнала x_i(t) устанавивается состояние a_і(t) управляемой МФСП, которое, при последующем воздействии сохраняющего входного сигнала e_j(Д), переводит состояние a_і(t) в новое состояние a_k(Д) в блоке м_і. При этом происходит укрупненный переход в новый блок р_j состояний схемы памяти (см. табл. 1). При запоминании в МУСП возникает качественно новая вертикальная иерархическая взаимосвязь состояний, которая определяет блоки р_j состояний а_і управляемых МФСП зависимо от запоминающих состояний a_k управляющих МФСП.

МУСП с многофункциональной системой организации определяет такую структуру, в которой многофункциональный режим работы одного устройства определяется другим устройством, так называемым автоматом стратегии А_М. Автомат стратегии А_М в МУСП может быть моно- и многофункциональным устройством памяти. В зависимости от возможностей автомата стратегии А_М МУСП с многофункциональной системой организации можно определить как открытою, полуоткрытою или закрытою структурою.