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

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

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

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) в связи с тем, что все ее 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 управляющих МФСП.

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

Рассмотрим открытые и полузакрытые структуры устройств памяти.

Определение 5. Открытою многоуровневою структурою устройства памяти МУСП с многофункциональною системою организации назовем автомат, который состоит из двух устройств: управляемой МФСП А_у и многофункционального автомата стратегии А_М, которые имеют объединенные множества состояний, входные Х и выходные Y алфавиты и сохраняющий входной алфавит Е_Н автомата стратегии А_М.

Открытую многоуровневую структуру устройства памяти МУСП с многофункциональною системою организации иллюстрирует рис. 9. Такая структура позволяет расширить многофункциональность, используя дополнительный автомат стратегии.

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

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

МФСП вместе с автоматом стратегии может создавать полузакрытые или открытые многоуровневые структуры устройств памяти с многофункциональною системою организации.

Иерархический абстрактный автомат А с памятью на МФСП рассматривается как g-ступенчатое (g > 1) устройство, состоящее из регистров R_j(j = 1, 2, …, g), которые взаемодействуют одновременно, и двух комбинационных схем КС1_і, КС2_і (і = 1, 2, ..., g) на каждой ступени. На уровне g (верхнему) иерархический g-ступенчатый автомат А способен функционировать как многофункциональный автомат 1-го, 2-го, а также 3-го рода, который имеет (g-1)-ступенчатый автомат стратегии А_М, использующийся для сохранения определенного блока р_і состояний соответствующего автомата на уровне g.

Каноническую структуру g-ступенчатого абстрактного автомата 1-го, 2-го и 3-го рода на МФСП одновременно с (g - 1)-ступенчатым автоматом стратегии изображено на рис. 11 --13.

В отличии от автоматов Мили (1-го рода) и Мура (2-го рода) с памятью на триггерах, функционирование которых рассматривается в автоматном дискретном времени, автоматы Мараховского на МФСП , функционирование которых рассматривается в автоматном непрерывном времени [64], способны при различных входных сигналах е_j(Д) запоминать состояния определенных блоков (подмножеств) р_j(р_jQ). В соответствии с этой способностью можно в каждом из блоков р_j(р_jQ) реализовать различные монофункциональные автоматы Мили и Мура, а также, воспользовавшися разными блоками р_j(р_jQ) памяти МФСП g-уровня и реализовать многофункциональные автоматы 1-го и 2-го рода (рис. 11-12).

Регистр R_g на МФСП и комбинационные схемы (КС) - это устройства, которые используются для обработки частной информации верхнего g-уровня. Каждое такое устройство можно описать как абстрактный автомат, который обрабатывает входную информацию и сохраняющие е_j(Д) входные сигналы которого, принадлежащие множеству Е_g (е_j(Д) Е_g), поступают из (g-1)-уровневого автомата стратегии (рис. 11)

Таким образом, приходим к выводам, что автоматы Мили и Мура, которые используют память на триггерах, являются частным случаем автоматов М, которые реализуют свою память на МФСП.

Показано, что, автоматы М g-уровневой ступени на МФСП одновременно с (g-1)-уровневым автоматами стратегии А_М имеют уникальную способность обрабатывать частную и общую информацию за один такт машинного времени.

Показано, что автоматы М g-уровневой ступени на МФСП имеют качественно новые (по сравнению с автоматами на триггерах) переходы из одного состояния в другое под воздействием е_j(Д) входных сигналов: укрупненные, вероятностные и нечеткие.

8. Понятие об абстрактных вероятностных автоматах 3-го рода

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

Талантливый математик Фрэнк Пламптон Рамсей доказал, что полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру [144].

Основным элементом человеческого мозга является нейрон, важнейшую роль в котором играют перестройки надмолекулярных структур в различных частях нервной клетки, а также волны структурных перестроек, сопровождающие передачу информации в пределах данного нейрона и от нейрона к другому нейрону [101]. Нейронную память представляют в матричном виде, управляемую по двум координатам возбуждающими и тормозящими входными сигналами и способную выполнять структурную перестройку передачи информации в иерархических ансамблях нейронов [37-38].

Рассматриваемые многофункциональные автоматы 3-го рода способны переходить в новое состояние по двум координатам (переменным) информационных (устанавливающих) и сохраняющих входных сигналов и осуществлять структурную перестройку подмножеств запоминаемых состояний, которую можно сравнить с работой нейрона [37-38]. В связи с этим представляет интерес исследование функционирования многофункциональных автоматов 3-го рода при поступлении на них вероятностных или нечетких входных слов.

Вероятностные переходы в автоматах 3-го рода происходят под воздействием вероятностных элементарных р_в1(Т) входных слов автоматного непрерывного времени двух типов:

р_в1(Т) = х_р(t), e_j(?),(18)

где х_р(t) -информационный входной сигнал (х_рХ), который однозначно устанавливает состояние памяти автомата, не сохраняемое ни при одном сохраняющем e_j(?) входом сигнале;

р_в2(Т) = х_і(t), (?),(19)

где (?) - вероятностный сохраняющий входной сигнал (Е).

Информационный х_р(t) входной сигнал (х_рХ) в детерминированных автоматах является запрещенным, так как устанавливает на выходных узлах схем памяти выходной сигнал, который не сохраняется ни при одном сохраняющем e_j(?) входом сигнале и ведет к вероятностным переходам, что не разрешено (просто запрещено).

Вероятностное слово первого типа (18) позволяет осуществлять вероятностный переход в тактовый внутренний момент ? из а_р(t) состояния, которое не запоминается, в неопределенное состояние вполне определенного р_j блока состояний автомата, под воздействием сохраняющего e_j(?) входного сигнала.

Вероятностное слово второго типа (19) позволяет осуществлять вероятностный переход в тактовый внутренний момент ? из определенного а_і(t) состояния в неопределенное состояние вполне определенного м_і блока состояний под воздействием вероятностного сохраняющего (?) входного сигнала.

Таким образом, вероятностные переходы в автоматах 3-го рода способны осуществлять переходы из одного состояния в состояние определенного блока состояний с определенной мерой вероятности.

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

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

Теорию Рамсея можно сформулировать в ещё более общем виде. Если число объектов в совокупности достаточно велико и каждые два объекта связывает одно из набора отношений, то всегда существует подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношением одного типа.

Есть некая ирония в том, каким образом за два года до смерти Рамсей вывел теорию, ныне называемую его именем. Он пришёл к основной идее, пытаясь доказать тезис, выдвинутый Расселом и Альфредом Нортом Уайтхедом в их основополагающем труде «Principia Mathematica» (Основы математики). Они предположили, что все математические истины могут быть выведены из ограниченного набора аксиом. Развивая эту идею, немецкий математик Давид Гильберт предположил, что должна существовать процедура, позволяющая решить, следует ли то или иное утверждение из данного набора аксиом или нет. Рамсей показал, что в некотором частном случае такая процедура принятия решения существует. (Спустя несколько лет Курт Гёдель и его последователи, англичанин Алан Тьюринг и другие, исчерпывающим образом доказали, что в общем случае такой процедуры не существует.)

Усилиями Рамсея, Эрдёша, Ван дер Вардена и многих других были заложены основы теории, носящей имя Рамсея. Для нас очень важен сам результат теории Рамсея, утверждающий, что каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру [133; 144]. С этой точки зрения мы и подходим к созданию вероятностных и нечетких автоматов 3-го рода.

Рассмотрим два типа вероятностных абстрактных автомата 3-го рода в зависимости от типов элементарных входных слов (18 -19).

Вероятностное слово первого типа (18) определяет функционирование вероятностного абстрактного автомата 3-го рода первого типа.

Вероятностный абстрактный автомат 3-го рода первого типа задается следующим определением.

Определение 7. Математическою моделью вероятностного устройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный вероятностный автомат А_В1 определяемый как десятикомпонентный кортеж или вектор [64]:

А_В1 = (х_р, Е, , Q, р, e₀, a₀, a_р, д_o, , , Р_е), (20)

у которого:

· х_р, - информационный входной сигнал (входной информационный алфавит);

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

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

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

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

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

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

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

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

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

· Р_е(а_ре_j) - система условных вероятностей.

Система условных вероятностей Р_е, заданных для каждой пары (а_р(t), е(?)) на множестве р_j ( р_j Q; Y_III, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у_k(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а_р(t), которое не запоминается, и на его входы подан сохраняющий е_j(?) входной сигнал, способный сохранять все множество состояний блока р_j состояний (а_s р_j).

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

(21)

Вероятностное слово второго типа (19) определяет вероятностный абстрактный автомат 3-го рода второго типа.

Вероятностный абстрактный автомат 3-го рода второго типа задается следующим определением.

Определение 8. Математическою моделью вероятностного устройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный вероятностный автомат А_В2 определяемый как одиннадцатикомпонентный кортеж или вектор [64]:

А_В2 = (Х, Е_в2, , Q, р, e₀, a₀, д_o, , , Р⁽⁰⁾, Р_е), (22)

у которого:

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

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

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

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

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

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

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

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

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

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

· Р⁽⁰⁾={P₀, P₁, P₂, …, P_k-1,} -начальное распределение вероятностей блока р_j состояний автомата;

· Р_е(а е^В2_j) - система условных вероятностей.

Система условных вероятностей Р_е, заданных для каждой пары (а(t), е^В2_j (?)) на множестве р_j ( р_j Q; Y_III, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у^в2(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а(t) и на его входы подан вероятностный сохраняющий е^В2_j (?) входной сигнал, способный сохранять все множество состояний блока р_j состояний (а_s р_j).

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

(23)

Смысл понятия абстрактного вероятностного автомата 3-го рода состоит в реализации некоторого вероятностного отображения ш_в множества вероятностных слов р_в(Т) входных алфавитов в множество слов у^в(?) выходного алфавита, символы которых принадлежат вполне определенным подмножествам Y_III. Появление каждого символа выходной последовательности зависит и определяется системой условных вероятностей в соответствии с типом абстрактного вероятностного автомата 3-го рода.

9. Понятие об абстрактных нечетких автоматах 3-го рода

Абстрактные нечеткие автоматы 3-го рода рассматриваются при поступлении на их входные узлы элементарных нечетких р_н(Т) входных слов (р_н(Т) = х_р(t), е_в(?)) в автоматном непрерывном времени Т.

Определение 9. Математическою моделью нечеткого устройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный нечеткий автомат М определяемый как четырнадцатикомпонентный кортеж или вектор [64]:

А_н = (х_р, Е, Е_в, , Q, Q_н, р, e₀, a₀, д_o, , , Р⁽⁰⁾, Р_е), (24)

у которого:

· х_р - информационный входной сигнал (входной информационный алфавит);

· Е = множество сохраняющих входных сигналов (входной сохраняющий алфавит);

· Е_Н = {} - множество нечетких сохраняющих входных сигналов (входной нечеткий сохраняющий алфавит, где );

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

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

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

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

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

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

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

· : Q Е_Н> р_j - функция нечеткого укрупненного перехода, реализующая отображение в р_j. Другими словами, функция некоторым парам „ несохраняемое состояние - нечеткий сохраняющий входной сигнал” (а_р(t), е^Н(?)) ставит в соответствие состояние автомата а(?)= (а_р(t), е^Н(?)), где а_р(t)р_і, а(?)р_j, а_р(t) ? а(?);

· : Q_Н Е_Н> - нечеткая функция выходов, реализующая отображение в . Другими словами, функция : некоторым парам „несохраняемое состояние - нечеткий сохраняющий входной сигнал” (а_р(t), е^Н(?)) ставит в соответствие выходной сигнал автомата у^Н(?)=(а_р(t), е^Н(?)), где у^Н ;

· Р⁽⁰⁾={P₀, P₁, P₂, …, P_k-1,} -начальное распределение нечеткого подмножества Q_Н состояний автомата;

· Р_Н(а_р е^Н_j) - система условных вероятностей.

Система условных вероятностей Р_Н, заданных для каждой пары (а_р(t), е^Н(?)) на множестве Q_Н ( Q_Н Q; Y_iii, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у_k(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а_р(t) и на его входы подан нечеткий сохраняющий е^Н_j(?) входной сигнал, способный переводить автомат из а_р(t) состояния в а(?) состояние блока р_j состояний, который принадлежит нечеткому подмножеству Q_Н состояний (р_j Q_Н).

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

(25)

Смысл понятия абстрактного нечеткого автомата 3-го рода состоит в реализации некоторого нечеткого отображения ш_н множества элементарных нечетких слов р_в(Т) входных алфавитов в множество слов у^Н(?) выходного алфавита, символы которых принадлежат вполне определенным подмножествам . Появление каждого символа выходной последовательности зависит и определяется системой условных вероятностей в соответствии с системой условных вероятностей Р_Н абстрактного нечеткого автомата 3-го рода.

10. Классификация детерминированных абстрактных автоматов

Рассмотрим классификацию детерминированных абстрактных автоматов по использованию типов их выходных сигналов, как это осуществлено в классических абстрактных автоматах Мили, генерирующих

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

Функционирование многофункциональных автоматов Мараховского исследуется в автоматном непрерывном времени, а сами абстрактные автоматы, память которых реализованы на МФСП, определяют многофункциональный характер их работы и могут также классифицироваться по их типам выходных сигналов, как это осуществлено в классических автоматах Мили и Мура. Так, объединенный абстрактный многофункциональный М-автомат имеет возможность генерировать три типа (тип 1, тип 2 и тип 3) выходных сигналов у¹(t), у²(Т) и у³(Д). Сочетание в абстрактном многофункциональном автомате только двух типов (тип 1 и тип 2) выходных сигналов у¹(t) и у²(Т) можно по аналогии с объединенным автоматом Мили и Мура также назвать многофункциональным С-автоматом. Сочетание в абстрактном многофункциональном автомате только двух типов (тип 1 и тип 3) выходных сигналов у¹(t) и у³(Д) назовем многофункциональным R1-автоматом, а сочетание в абстрактном многофункциональном автомате только двух типов (тип 2 и тип 3) выходных сигналов у²(Т) и у³(Д) назовем многофункциональным R2-автоматом. Абстрактные многофункциональные автоматы, использующие только один тип выходных сигналов у¹(t), у²(Т) или у³(Д) назовем соответственно абстрактными многофункциональными автоматами 1-го, 2-го или 3-го рода.

Классификация абстрактных многофункциональных автоматов с памятью на МФСП представлена на рис. 14.

Отметим, что абстрактные монофункциональные автоматы Мили (1-го рода), Мура (2-го рода) и С-автомат являются частным случаем абстрактных многофункциональных автоматов 1-го, 2-го рода и С-автомата.

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

11.Классификация недетерминированных абстрактных автоматов

Рассматриваемые недетерминированные (вероятностные и нечеткие) абстрактные автоматы 3-го рода характеризуются осуществлением переходов по двум переменным за один такт Т автоматного непрерывного времени под влиянием элементарных вероятностных и нечетких входных слов.

Вероятностные абстрактные автоматы 3-го рода описывают вероятностные переходы из вполне определенного а(Д-1) состояния в состояние а(Д) целого подмножества состояний вполне определенного блока р_j состояний в соответствии с определенной вероятностью Р_е. Такие переходы могут быть конструктивными, если учесть, что они выполняются в аппаратуре устройств компьютера и могут быть определяемыми при испытаниях аппаратуры. Такие переходы могут быть очень полезны при использовании их в алгоритмах программ в связи с тем, что отсев ненужных вариантов повышает «машинный» интеллект программы.

Нечеткие абстрактные автоматы 3-го рода описывают нечеткие переходы из вполне определенного а(Д-1) состояния в состояние а(Д) целого нечеткого Q_н подмножества состояний, которое состоит из вполне определенных подмножеств блоков р_j состояний в соответствии с определенной вероятностью Р_н.

Такие переходы могут быть также конструктивными, если учесть, что они выполняются в аппаратуре устройств компьютера и могут быть определяемыми при испытаниях аппаратуры. Такие переходы также могут быть очень полезны при использовании их в алгоритмах программ в связи с тем, что отсев ненужных вариантов повышает «машинный» интеллект программы. Классификация абстрактных вероятностных и нечетких автоматов третьего рода представлена на рис. 15.

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

Объединенный абстрактный недетерминированный автомат можно рассматривать совместно с детерминированным абстрактным автоматом 3-го рода. При этом происходит использование соответствующих элементарных входных слов: однозначных, вероятностных первого и второго типа или нечетких.

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

Все абстрактные автоматы с 1-го по 3-й род рассматривают только область их функционирования в автоматном дискретном времени, или в автоматном непрерывного времени. В своем описания они не рассматривают возможность проверки схем памяти на работоспособность [13-14; 24-26; 32; 35; 64; 90; 119; 140].

Вопросы проверки работоспособности эдементарных автоматов в общем осуществляется схемотехническими средствами при наличии трех одинаковых устройств, которые через схему сравнения выдают сигнал, что схема работает верно или не верно [44-45].

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

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

В настоящее время большие интегральные схемы (БИС) строятся с расчетом на 100% работоспособность всех компонентов схемы. Увеличение числа компонентов и уменьшения их размеров увеличивает вероятность выхода из области работоспособности компонентов и появление обрывов в их связях. Это приводит к значительному брака кристаллов при построении БИС и к катастрофическому отказу их в процессе эксплуатации.

С целью увеличения надежности работы системы из ненадежных электронных элементов делается многократное резервирование, распределение сетевых систем и т.п., в которых отказ целого блока или устройства из строя определяется выходным сигналом схем сравнения нескольких блоков [5-7].

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

Катастрофических отказов в базовых схемах памяти существует два типа. Первый тип в базовых схемах памяти на логических элементах ИЛИ-НЕ (И-НЕ) осуществляется при появлении неизменного активного выходного сигнала хотя бы на одном из выходных узлов логических элементов, значение которых равно логической 1(0). Второй тип в базовых схемах памяти на логических элементах ИЛИ-НЕ (И-НЕ) осуществляется при появлении неизменных пассивных сигналов одновременно на всех выходных узлах логических элементах ИЛИ-НЕ (И-НЕ), значение которых равны логическому 0(1). Первый тип катастрофических отказов представляет собой активный постоянный выходной сигнал на выходном узле логического элемента, который по цепям к входам логических элементов других групп базовой схеме памяти делает схему памяти полностью не работоспособной. Такой же не работоспособной становится схема памяти при втором типе катастрофических отказов, когда на всех ее выходных узлах базовой схемы памяти значения пассивны. Такое состояние схемы памяти не запоминается ни при одном сохраняющем е(Д) входном сигнале. При ответственных устройствах управления в таких областях как: атомная электростанция, любой вид транспорта и т.д. катастрофические неконтролируемые отказы недопустимы, так как компоненты устройств и БИС должны работать надежно. Иначе, это приводит к большим катастрофам [8].

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

Все известные абстрактные и структурные автоматы с системных позиций, которые рассматривают законы работы каких-либо устройств с памятью, классифицируются по типу выходного сигнала [24; 64]. Для всех из них, работающих в детерминированном режиме, есть один устанавливающий х_р(t) входной сигнал, осуществляющий вероятностный переход (3.5) под действием сохраняющего е(Д) входного сигнала в определенный блок р_j состояний,_, который имеет для базовой схемы на всех ее входящих узлах активное значение, равное логической 1(0). Этот х_р(t) входной сигнал устанавливает на выходных узлах логических элементов ИЛИ-НЕ (И-НЕ) значение, равное логическому 0 (1). Такое состояние а_р(t) выходных сигналов не сохраняется при окончании устанавливающего сигнал х_р(t) и делает вероятный переход в состояние а(Д), которое затем запоминается в определенном множества р_j состояний схемы памяти. Поэтому, устанавливающий х_р(t) входной сигнал не используется в детерминированных автоматах и является запрещенным [64; 125].

Но, этот устанавливающий х_р(t) входной сигнал можно во всех рассмотренных автоматах 1-го, 2-го и 3-го рода использовать для определения выходных сигналов катастрофических отказов первого типа, когда у⁴(t) = л₄(х_р(t), a_р(t)), и использовать для определения выходных сигналов катастрофических отказов второго типа выходной сигнал вероятностного автомата 3-го рода у^в1(Д) = л₃(a_р(Д), е(Д)). Выходной сигнал у⁴(t) автомата 4-го рода отличается от выходного сигнала у¹(t) автомата 1-го рода тем, что использует в функции выходов не состояние a(Д-1), а состояние a_р(t), которое установлено устанавливающим х_р(t) входным сигналом. Таким образом, автомат, использующий выходной сигнал у⁴(t) можно назвать автоматом четвертого рода в связи с тем, что все автоматы определяются по своим выходным сигналам. На самом деле, выходной сигнал у⁴(t) может дополнительно добавляться в выходных сигналов любых автоматов с памятью на базовых схемах памяти. Выходной сигнал у^в3(Д) автомата 3-го рода появляется после вероятностного перехода схемы памяти в одно из запоминаемых состояний базовой схемы памяти при воздействии сохраняющего е(Д) входного сигнала.

Эти выходные сигналы у⁴(t) и у^в1(Д) можно использовать для проверки работоспособности элементов памяти в любых устройствах при выявлении их катастрофических отказов. Объясняется это тем, что при катастрофических отказах первого типа в схеме памяти автомата, когда хотя бы один логический элемент в памяти ИЛИ-НЕ (И-НЕ) имеет постоянный выходной сигнал, равный логическому 0 (1), то выходной сигнал у⁴(t) меняет свое значение, которое определяет отказ работоспособности памяти на противоположное значение 1 (0). Катастрофические отказы второго типа образуются и при отсутствии на всех выходных узлах схемы логической 1 и при поступлении на входные узлы сохраняющего е(Д) входного сигнала. Структурная схема автомата четвертого рода изображена на рис. 16.

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

Заключение

автомат триггер схема

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

Отмечено, что автоматы Мили и Мура являются частным случаем детерминированных автоматов Мараховского.

В данной работе также рассмотрены основные понятия абстрактных недетерминированных автоматов (вероятностных и нечетких) 3-го рода, реализуемых на схемах автоматной памяти.

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

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

Литература

1. Ricardo, Argenton Ramos AIRDoc - An Approach to Improve the Quality of Requirements Document / Ricardo Argenton Ramos. - М.: LAP Lambert Academic Publishing, 2017. - 128 c.

2. Администратор информационных технологий / IT Manager, №2, 2013. - М.: ИТ Медиа, 2017. - 970 c.

3. Администратор информационных технологий / IT Manager, №4, 2013. - М.: ИТ Медиа, 2016. - 312 c.

4. Алиев, В. С. Информационные технологии и системы финансового менеджмента / В.С. Алиев. - М.: ИНФРА-М, 2016. - 320 c.

5. Андерсон, Джордж У. Лучшие практики внедрения SAP / Андерсон Джордж У.. - М.: ЛОРИ, 2017. - 899 c.

6. Брусакова, И. А. Информационные системы и технологии в экономике / И.А. Брусакова, В.Д. Чертовской. - М.: Финансы и статистика, 2017. - 352 c.

7. Данелян, Т. Я. Экономические информационные системы (ЭИС) предприятий и организаций / Т.Я. Данелян. - М.: Юнити-Дана, 2015. - 284 c.

8. Демистификация ИТ. Что на самом деле информационные технологии дают бизнесу. - М.: Альпина Паблишер, 2015. - 296 c.

9. Журнал Windows IT Pro/RE, июнь 2013. - М.: Открытые Системы, 2016. - 244 c.

10. Затонский, А. В. Информационная поддержка принятия решений при управлении филиалом вуза / А.В. Затонский, С.А. Варламова, Е.В. Измайлова. - М.: РИОР, Инфра-М, 2016. - 334 c.

11. ИТ инфраструктура бизнеса / IT Expert, №3, 2013. - М.: ИТ Медиа, 2016. - 978 c.

12. ИТ инфраструктура бизнеса / IT Expert, №6, 2012. - М.: ИТ Медиа, 2015. - 593 c.

13. ИТ инфраструктура бизнеса / IT Expert, №7, 2012. - М.: ИТ Медиа, 2015. - 925 c.

14. Информационная Война Против Российской Федерации: Институализация Информационного Противоборства В Контексте Реализации Стратегии Национальной Безопасности Российской Федерации. Материалы Круглого Стола / Коллектив авторов. - Москва: Мир, 2016. - 113 c.

15. Информационные технологии в менеджменте (управлении). Учебник и практикум. - М.: Юрайт, 2015. - 480 c.

16. Информационные технологии для финансовых менеджеров. - М.: Издательский центр БГУ, 2017. - 480 c.

17. Компьютерное моделирование менеджмента / А.Ф. Горшков и др. - М.: Экзамен, 2016. - 528