авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 7 |

«Л. Ф. МАРАХОВСКИЙ ОСНОВЫ НОВОЙ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ Фундаментальные основы построения реконфигурируемых устройств компьютерных систем и ...»

-- [ Страница 2 ] --

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

а(t) = (а(t – 1), х(t)), у1(t) = 1(а(t – 1), х(t)), (t = 1, 2. …), (2.3) для автомата второго рода (автомата Мура), функционирующего в автомат ном дискретном времени, – уравнениями:

а(t) = (а(t – 1), х(t)), у2(t) = 2(а(t)), (t = 1, 2. …), (2.4), а в случае С-автомата, в котором реализовались функции выходов автоматов Мили и Мура – уравнениями:

а(t) = (а(t – 1), х(t)), у1(t) = 1(а(t – 1), х(t)), у2(t) = 2(а(t)), (t = 1, 2. …), (2.5) Установлением закона функционирования заканчивается определение абстрактного автомата. Смысл понятия абстрактного автомата состоит в реа лизации некоторого отображения множества слов входного алфавита в множество слов выходного алфавита. Отображение в автоматах Мили и Мура реализуется так: каждое слово р х i1, x i2,..., x ik входного алфавита Х = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установ ленного предварительно в начальное состояние а0. Возникающая таким обра А зом конечная последовательность входных сигналов, автомата x(1) х,..., x(k ) x, на основании закона функционирования автомата вы i1 ik зывает появление однозначно определенной конечной последовательности q= y(1), y(2), …, y(k) выходных сигналов. Эту последовательность называют выходным словом, соответствующим входному слову р. Допустимыми входными словами называются те и только те входные слова р, на которых с помощью функций и (описанным выше способом) определяются соответствующие выходные слова q=(р).

Входные сигналы автомата Мили Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы а Входные сигналы автомата Мура Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы б Входные сигналы Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.2. Структурные схемы монофункциональных автоматов 1-го и 2-го рода Построенное указанным способом искомое отображение, а именно: q = =(р), называют отображением, индуцированным абстрактным автома том А.

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

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

Каноническая схема автомата Мили (рис. 2.2, а), автомата Мура (рис. 2.2, б) или С-автомата в обобщенном виде (рис. 2. 2, в) состоят из, связан ных между собою, регистра и комбинационных схем.

Монофункциональный автомат имеет жесткую структуру и всегда реа лизует одно и то же преобразование {X} в {Y}. Для такого автомата величина функциональности f равна 1 (f = 1).

2.3. Понятие об многофункциональных абстрактных автоматах Мили и Мура С конца 60-х и начала 70-х годов ХХ века начались исследования после довательных многофункциональных логических устройств [32;

90–91;

138;

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

Основа многофункциональных автоматов Мили и Мура была положена в структуры реконфигурируемых устройств компьютерной техники, в их ал горитмическое управление и в программное обеспечение искусственного ин теллекта [16;

23;

25;

30;

33;

39;

41–42;

47;

52;

88;

91;

98;

102;

109–112;

116;

124;

132–134;

142].

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

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

А = (Х, Y, Q,,, Q0, U, f), (2.6) где Х – конечное множество входных сигналов, называемых входным алфавитом;

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

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

Q0 – множество из множества Q, называемым начальным множе ством состояний автомата (Q0Q);

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

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

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

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

( f i. :U U i i, i 1, L, L Q).

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

Аі = (Хі, Yі, Qі, (і), (і), а(і)0), (2.7) в котором компоненты автомата не отличаются от компонентов, описанных в (2.2) Исходя из уравнений (2.3) и (2.4) функционирования монофункциональ ных автоматов 1-го и 2-го рода, получим уравнения законов функционирова ния детерминированных многофункциональных абстрактных автоматов та ких же типов 1-го и 2-го рода:

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

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), (2.8) (t = 1, 2. …, i = 1, 2, …L), для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, – уравнениями:

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t), U(і)), (2.9), (t = 1, 2. …, i = 1, 2, …L), а, в случае, объединенного С-автомата, в котором реализуются функции вы ходов автоматов Мили и Мура – уравнениями:

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у1(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t), U(і)), (2.10) (t = 1, 2. …? i = 1, 2, …L), Смысл понятия многофункционального абстрактного автомата состоит в реализации некоторого множества отображений i множества слов входного i-го алфавита в множество слов выходного i-го алфавита. Отображение i в автоматах Мили и Мура реализуется так: каждое слово рi х i1, x i2,..., x ik входного i-го алфавита Хi = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстракт ного автомата Аi из множества многофункционального автомата А, установ ленного предварительно в начальное состояние а(i)0. Возникающая таким об разом конечная последовательность рi входных сигналов, автомата Аi x x(1), х(2),..., x(k ), на основании закона функционирования автомата вы ik зывает появление однозначно определенной i-й конечной последовательно сти qi= y(1), y(2), …, y(k) выходных сигналов. Эту последовательность qi на зывают выходным i-м словом, соответствующим входному слову рi. Допус тимыми входными словами называются те, и только те, входные слова рi, на которых с помощью функций (і) и (і) (описанным выше способом) опреде ляются соответствующие выходные слова qi=(рi).

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

Монофункциональные и многофункциональные автоматы 1-го и 2-го рода и их объединение С-автомат [21;

24–26;

32;

90], реализующие свою ре гистровую память на триггерах и функционирование которых рассматривает ся в автоматном дискретном времени, являются частным случаем автоматов Мараховского (многофункциональных автоматов 1-го и 2-го рода) [55].

U Входные сигналы автомата Мили U Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы а U Входные сигналы автомата Мура U Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы б Входные сигналы U U Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.3. Структурные схемы многофункциональных автоматов Мили и Мура с настройками U и U из автомата стратегии Автоматы Мараховского реализуют свою регистровую память на схемах автоматной памяти, и функционирование их рассматривается в автоматном непрерывном времени.

2.4. Некоторые понятия об изменениях в функционировании и самоорганизации в автоматах При решении различных задач теории автоматов часто возникают до полнительные условия на рассматриваемые автоматы, определяющие те или иные подклассы класса всех конечных автоматов [59;

93]. Одним из таких условий является понятие многофункциональных автоматов совместно с ав томатами настройки (автоматами стратегии).

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

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

Входные сигналы автомата настройки Автомат настройки (стратегии) U U U Входные сигналы U U Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.4. Обобщенная структурная схема многофункциональ ного автомата Мили и Мура с автоматом настройки (стратегии) При рассмотрении теории самоорганизующих систем (автоматов, алго ритмов) весьма существенным являются понятия одномерной и многомерной случайной величины, значениями которых являются конечные упорядочен ные наборы вещественных чисел или, иначе говоря, вещественные векторы той или иной (конечной) размерности.

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

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

f ( xi ) 1, (2.11) i где суммирование предполагается распространенным на всю область опре деления данной случайной величины.

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

Работа реального устройства, которое исследуется в моделях автоматов Мили и Мура, наблюдается лишь в выделенные моменты времени t1, t2, и т.д.

Изменения, происходящие с устройством, между наблюдаемыми моментами с точностью до несущественных деталей определяются информацией в мо менты t1, t2 и т.д. Одно из возможных обобщений этого допущения заключа ется в рассмотрении двух независимых последовательностей времени t1, t2 и 1, 2, таких, что в моменты t1, t2 наблюдаются поступающие на входные узлы внешние сигналы, а в моменты 1, 2 – наблюдаются выходные сигналы уст ройства. При этом предполагается, что устройство имеет функцию перехода.

Эта функция однозначно определяется по входному сигналу и состоянию устройства и описывается уравнением (2.3) во времена t1, t2, …. Выходные сигналы устройства определяются во времени 1, 2, …, которые определятся соотношениями: tn s s+1…s+l tn+1, и однозначно определяются по входному сигналу и состоянию устройства в момент времени tn.

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

Абстрактный конечный асинхронный автомат определяется как автома ты Мили и Мура, но без начального состояния. Асинхронные автоматы реа лизуют преобразования слов из входного алфавита Х* в выходной алфавит 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].

2.6. Понятие об абстрактных многофункциональных автоматах Мараховского Функционирование абстрактных многофункциональных автоматов Ма раховского, построенных на схемах автоматной памяти [64], рассматривается в автоматное непрерывное время (рис. 1.3).

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

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

А = (Х, Y, Q,,, е, a0, e), (2.12) у которого:

компоненты Х, Y, Q,, и a0 имеют те же значения и тот же смысл, что и при описании вектора (2.2);

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

е: Q е Q – функция сохранения состояния, реализующее ото бражение De Qe на Q, при котором произвольное состояние aі(aі Q) сохраняет свое значение.

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

х(t) е(t)= х(t) (2.13) Структуру восьмикомпонентного монофункционального абстрактного автомата А в обобщенном виде представлена на рис. 2.5.

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

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

64].

Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою подмножества µi ( Q) состояний i j i автомата, а строки – подмножества j Q) состояний автомата ( j j (табл. 2.1).

Таблица 2. Матрица состояний схемы автоматной памяти µ1 µ2 ….. µn 0 a10 a20 … an 1 a11 a21 … an 2 a12 a22 … an …… … … … m a1m a2m … anm Триггеры и многостабильные схемы памяти (МСП) можно представить как строку 0 автоматной матрице (табл. 2.1) в связи с тем, что все ее ai со стояния сохраняются при одном сохраняющем е() входном сигнале в одном множестве всех его состояний. Эти схемы обладают полнотой функций пере ходов, когда из каждого ak состояния можно под воздействием определенно го входного х(t) сигнала перейти в любое, наперед заданное, ai состояние схемы памяти;

а также полнотой системы выходов, когда каждое ai состояние отождествляется с выходным уi сигналом, который отличный от всех других.

В многофункциональной схеме автоматной памяти (МФСП) [63] пере ходы в момент t под воздействием входных х(t) сигналов могут происходить из одного состояния в другое в определенном подмножестве i, а в моменты автоматного непрерывного времени Т под воздействием входного е() сиг нала могут происходить переходы из одного состояния в другое в определен ном подмножестве µi состояний автомата. Таким образом, в матричной схеме автоматной памяти возможны переходы по двум переменным х(t) и е() в одном машинном такте Т автоматного непрерывного времени [64].

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

А = (Х, Е, YI, YII, YIII, Q,, e0, a0, o, e, y, 1, 2, 3), (2.14) у которого:

Х = {x0, x1,…, xN-1} – множество информационных входных сигна лов (входной информационный алфавит);

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

YI = { Y01, Y11,...,YK 1 } – множество выходных сигналов типа 1 (выход ной алфавит типа 1):

YII = { Y02, Y12,...,YK2 1 } – множество выходных сигналов типа 2 (вы ходной алфавит типа 2);

YIII = { Y03, Y13,...,YK3 1 } – множество выходных сигналов типа 3 (вы ходной алфавит типа 3);

Q = {a0, a1,…, am1} – произвольное множество состояний (алфавит состояний);

= { 0, 1,…, R-1} –множество блоков j состояний (алфавит бло ков состояний);

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

a0 0 ( j Q) – начальное состояние автомата;

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

e: функция сохранения состояний блока j при а j, реализующая отображение D Q e в j. Другими словами, функция е: неко j e торым парам „состояние – сохраняющий входной сигнал” (а(t), е()) ставит в соответствие состояние автомата а()= е(а(t), е()), где а j, а(t) = а() (j Q);

y: Q E j – функция укрупненных переходов, реализующая отображение D Q e в j. Другими словами, функция у неко j y торым парам „состояние – сохраняющий входной сигнал” (а(t), е()) ставит в соответствие состояние автомата а()= у(а(t), е()), где а(t) p, а() j, а(t) а() (а(t), а() Q);

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

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

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

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

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

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

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

a(t ) (a( 1), x(t ));

a() e (a(t ), e());

(2.15) y1 (t ) 1 (a( 1), x(t )), L a(t ), a() ;

i 0, 1, 2,...;

0, 1, 2,....

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

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

a(t ) (a( 1), x(t ));

a() e (a(t ), e());

(2.16) y L (T ) 2 (a(t ), a()), a(t ), a() ;

i 0, 1, 2,...;

0, 1, 2,....

j В каждый момент ti автомат 3-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информацион ного алфавита Х и осуществлять переход в новое состояние а(t), а также спо собен воспринимать сохраняющийся входной сигнал еj()– произвольную бу кву входного сохраняющего алфавита Е и осуществлять в каждый момент i переход в новое состояние а() входящего в подмножество µi множество со стояний Q (µi Q), а также выдавать соответствующий выходной сигнал у3() – некоторую букву выходного алфавита YIII.

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

a(t ) (a( 1), x(t ));

a() y (a(t ), e());

(2.17) y L () 3 (a(), e()), a(t ), a() ;

i 0, 1 2,...;

, 0, 1, 2,....

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

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

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

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

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

В момент такта t под воздействием входной х(t) буквы входного инфор мационного алфавита Х автомат М способен перейти в новое состояние аi подмножества состояний i, а потом перейти в новое состояние аk подмноже ства состояний j при входной букве еj() входного сохраняющего алфавита Е автомат М, и входящего во множество состояний Q (i Q), а также выда вать соответствующий выходной сигнал у3() – некоторую букву выходного алфавита YIII.

Возникающие таким образом конечные последовательности входных элементарных слов р(Т) = х(t), е() на основании законов функционирования автомата в автоматном непрерывном времени Т вызывают соответственно определенные конечные последовательности qi= i(p) выходных букв из со ответствующих входных алфавитов YI, YII, YIII. Эту последовательность qi на зывают выходным словом автомата 1-го, 2-го или 3-го рода обобщенного ав томата М.

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

Х Y А Y Y Е Рис. 2.6. Структурная схема абстрактного М-автомата А Абстрактный М-автомат А, который описывается вектором (2.14), имеет два входа Х и Е и три выхода Y1, Y2, Y3 (рис. 2.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-го рода. Структурная схема многофунк ционального автомата М представлена на рис. 2.7.

у1(t) у2(Т) у3() комбинацион- комбинацион- комбинацион ная схема ная схема ная схема выходов выходов выходов типа 1 типа 2 типа РЕГИСТР комбинационная схема функций возбуждения комбинационная схема сохране ния состояний х(t) е() Рис. 2.7. Состав структурной схемы абстрактного многофункцио нального М-автомата 2.7. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний Многофункциональные автоматы на схемах автоматной памяти имеют возможность с помощью автомата настройки U выполнять комутацию функций возбуждения и выходов, как это осуществлялось при реализации в автоматах с памятью на триггерах (рис. 1.4), а также с помощью g-ступенчатого автомата А, имеющего (g-1) автомат стратегии АМ, который генерирует сохраняющие е() входные сигналы для абстрактного М-автомата А и выполняет перестройку (регенерацию) функций сохранения состояний многофункциональной памяти автомата Ау, что является новым в теории ие рархических, многофункциональных автоматов.

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

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

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

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

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

Входные сигналы автомата А Комбинационные схемы Регистр Rg Выходные сигналы U U автомата А (g-1)-ступенчатого ав Автомат настройки U томата стратегии АМ Входные сигналы автомата настройки U Входные сигналы (g-1)-ступенчатого автомата стратегии АМ Рис. 2.8. Обобщенная структурная схема многофункционального автомата А на схемах автоматной памяти Под воздействием входного сигнала xi(t) устанавивается состояние aі(t) управляемой МФСП, которое, при последующем воздействии сохраняющего входного сигнала ej(), переводит состояние aі(t) в новое состояние ak() в блоке і. При этом происходит укрупненный переход в новый блок j состояний схемы памяти (см. табл. 2.1). При запоминании в МУСП возникает качественно новая вертикальная иерархическая взаимосвязь состояний, которая определяет блоки j состояний аі управляемых МФСП зависимо от запоминающих состояний ak управляющих МФСП.

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

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

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

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

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

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

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

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

ху уу Ау Х Ey уМ Y хМ АМ уH EH Рис. 2.9. Открытая многоуровневая структура ху уу Ау Y Х Ey уМ хМ АМ Рис. 2.10. Полузакрытая многоуровневая структура А Иерархический абстрактный автомат с памятью на МФСП рассматривается как g-ступенчатое (g 1) устройство, состоящее из регистров Rj(j = 1, 2, …, g), которые взаемодействуют одновременно, и двух комбинационных схем КС1і, КС2і (і = 1, 2,..., g) на каждой ступени. На уровне g (верхнему) иерархический g-ступенчатый автомат А способен функционировать как многофункциональный автомат 1-го, 2-го, а также 3-го АМ, рода, который имеет (g–1)-ступенчатый автомат стратегии использующийся для сохранения определенного блока і состояний соответствующего автомата на уровне g.

Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.11. Структурная схема автомата 1-го рода (открытая g-уровневая структура) Каноническую структуру g-ступенчатого абстрактного автомата 1-го, 2 го и 3-го рода на МФСП одновременно с (g – 1)-ступенчатым автоматом стратегии изображено на рис. 2.11 —2.13.

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

Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.12. Структурная схема автомата 2-го рода (открытая g-уровневая структура) Регистр Rg на МФСП и комбинационные схемы (КС) – это устройства, которые используются для обработки частной информации верхнего g уровня. Каждое такое устройство можно описать как абстрактный автомат, который обрабатывает входную информацию и сохраняющие еj() входные сигналы которого, принадлежащие множеству Еg (еj() Еg), поступают из (g–1)-уровневого автомата стратегии (рис. 2.11) Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.13. Структурная схема автомата 3-го рода (открытая g-уровневая структура) Таким образом, приходим к выводам, что автоматы Мили и Мура, кото рые используют память на триггерах, являются частным случаем автоматов М, которые реализуют свою память на МФСП.

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

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

укрупненные, вероятностные и нечеткие.

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

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

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

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

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

рв1(Т) = хр(t), ej(), (2.18) где хр(t) –информационный входной сигнал (хр Х), который однозначно ус танавливает состояние памяти автомата, не сохраняемое ни при одном со храняющем ej() входом сигнале;

и рв2(Т) = хі(t), e вj (), (2.19) где e вj () – вероятностный сохраняющий входной сигнал ( e вj Е).

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

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

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

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

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

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

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

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

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

144]. С этой точки зрения мы и подходим к созда нию вероятностных и нечетких автоматов 3-го рода.

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

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

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

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

yB, 3, Ре), АВ1 = (хр, Е, YIII, Q,, e0, a0, aр, o, B B (2.20) у которого:

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

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

YIII B = { Y0B1, Y1B1,...,YKB11 } – множество вероятностных выходных сиг налов типа 3 (выходной вероятностный алфавит типа 3);

Q = {a0, a1,…, am1} – произвольное множество запоминаемых со стояний автомата (алфавит состояний);

= {0, 1,…, R-1} –множество блоков j состояний (алфавит бло ков состояний);

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

Q) a0 0 ( j – начальное состояние автомата;

j o: Q хр ар, – однозначная функция перехода, реализующая отображение D Q x p в ар,. Другими словами, функция o: не которым парам „состояние – информационный входной сигнал” (а(-1), хр,(t)) ставит однозначно в соответствие несохраняемое со стояние автомата ар(t) = o(а(-1), хр(t)), где ар Q;

B1 : ар E j – функция вероятностного укрупненного перехода, y реализующая отображение D a e в j. Другими словами, p j y функция B1 некоторым парам „несохраняемое состояние – сохра y няющий входной сигнал” (ар(t), е()) ставит в соответствие состоя ние автомата а()= B1 (ар(t), е()), где ар(t) j, а() j, ар(t) y а();


3 1 : Q E YIII1 –вероятностная функция выходов типа 3, реали B B зующая отображение D a Е в YIII1. Другими словами, функ B p ция B1 : некоторым парам „несохраняемое состояние – сохраняю щий входной сигнал” (ар(t), е()) ставит в соответствие выходной сигнал автомата ув1()= B1 (ар(t), е()), где у YIII1 ;

B Ре(ареj) – система условных вероятностей.

Система условных вероятностей Ре, заданных для каждой пары (ар(t), е()) на множестве j YIII1 ( j Q;

YIII1 YIII, где YIII выходные сигналы авто B B мата 3-го рода) характеризует вероятность перехода автомата в состояние аs() с выдачей сигнала уk(), который отображает состояние аs() автомата, при условии, что автомат предварительно был установленный в состояние ар(t), которое не запоминается, и на его входы подан сохраняющий еj() входной сигнал, способный сохранять все множество состояний блока j со стояний (аs j).

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

а (t ) (a( 1), x (t ));

р р (2.21) a() B1 (a p (t ), e(), Pe );

y B1 () (a(), e()), L a(t ) j, a() j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 Pe 1.

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

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

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

АВ2 = (Х, Ев2, YIII2, Q,, e0, a0, o, y 2, 3 2, Р(0), Ре), (2.22) B B B у которого:

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

Ев2 = { e1B 2, e2B 2,... e R 1 } – множество вероятностных сохраняющих B входных сигналов (входной вероятностный сохраняющий алфа вит);

YIII2 = { Y0B 2, Y1B 2,...,YKB 21 } – множество вероятностных выходных сиг B налов типа 2 (выходной вероятностный алфавит типа 2);

Q = {a0, a1,…, am1} – произвольное множество запоминпемых со стояний (алфавит состояний);

= {0, 1,…, R-1} –множество блоков j состояний (алфавит бло ков состояний);

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

a0 0 ( j Q ) – начальное состояние автомата;

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

B2 : Q Ев2 j – функция вероятностного укрупненного перехо y да, реализующая отображение D Q E в j. Другими словами, B2y функция B 2 некоторым парам „состояние – вероятностный сохра y няющий входной сигнал” (а (t), еВ2()) ставит в соответствие со стояние автомата а()= B 2 (а(t), еВ2()), где а(t) і, а() j, y а(t) а() (а (t), а()Q);

3 2 : Q Ев2 YIII2 –вероятностная функция выходов типа 3, реали B B зующая отображение D Q Е в YIII2. Другими словами, функ B B ция B2 : некоторым парам „состояние – вероятностный сохраняю щий входной сигнал” (а (t), еВ2()) ставит в соответствие выходной сигнал автомата ув2()= B 2 (а (t), еВ2()), где у YIII2 ;

B Р(0)={P0, P1, P2, …, Pk-1,} –начальное распределение вероятностей блока j состояний автомата;

Ре(а еВ2j) – система условных вероятностей.

Система условных вероятностей Ре, заданных для каждой пары (а(t), еВ2j ()) на множестве j YIII2 ( j Q;

YIII2 YIII, где YIII выходные сигналы ав B B томата 3-го рода) характеризует вероятность перехода автомата в состояние аs() с выдачей сигнала ув2(), который отображает состояние аs() автомата, при условии, что автомат предварительно был установленный в состояние а(t) и на его входы подан вероятностный сохраняющий еВ2j () входной сиг нал, способный сохранять все множество состояний блока j состояний (аs j).

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

a(t ) (a( 1), x(t ));

(2.23) a() B 2 (a(t ), e j (), P0, Pe );

B B y L () в 2 (a(), e()), a(t ) j, a() j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 P 1;

0 Pe 1.

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

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

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

Ан = (хр, Е, Ев, Y H, Q, Qн,, e0, a0, o, H, 3, Р(0), Ре), H (2.24) III y у которого:

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

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

ЕН = { e1Н, e2Н,... e R 1 } – множество нечетких сохраняющих входных Н сигналов (входной нечеткий сохраняющий алфавит, где Е) );

( Е H j Y H = { Y0Н, Y1Н,...,YKН 1 } – множество нечетких выходных сигналов III автомата 3-го рода (выходной нечеткий алфавит);

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

QН = {a0, a1,…, am1} – произвольное нечеткое подмножество со стояний (алфавит нечетких подмножеств состояний, где Q) );

( Q H j = {0, 1,…, R-1} –множество блоков j состояний (алфавит бло ков состояний);

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

a0 0 ( j Q) – начальное состояние автомата;

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

H: Q ЕН j – функция нечеткого укрупненного перехода, реа y лизующая отображение D Q E в j. Другими словами, функ Н y ция H некоторым парам „ несохраняемое состояние – нечеткий y сохраняющий входной сигнал” (ар(t), еН()) ставит в соответствие состояние автомата а()= H (ар(t), еН()), где ар(t)і, а()j, y ар(t) а();

Н : QН ЕН YIII – нечеткая функция выходов, реализующая ото Н Н бражение D Q Е в YIII. Другими словами, функция 3 :

Н Н Н некоторым парам „несохраняемое состояние – нечеткий сохра няющий входной сигнал” (ар(t), еН()) ставит в соответствие вы ходной сигнал автомата уН()= 3 (ар(t), еН()), где уН YIII ;

Н Н Р(0)={P0, P1, P2, …, Pk-1,} –начальное распределение нечеткого под множества QН состояний автомата;

РН(ар еНj) – система условных вероятностей.

Система условных вероятностей РН, заданных для каждой пары (ар(t), еН()) на множестве QН YIII ( QН Q;

YIII Yiii, где YIII выходные сигналы Н Н автомата 3-го рода) характеризует вероятность перехода автомата в состоя ние аs() с выдачей сигнала уk(), который отображает состояние аs() авто мата, при условии, что автомат предварительно был установленный в состоя ние ар(t) и на его входы подан нечеткий сохраняющий еНj() входной сигнал, способный переводить автомат из ар(t) состояния в а() состояние блока j состояний, который принадлежит нечеткому подмножеству QН состояний (j QН).

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

a (t ) (a( 1), x (t ));

р р a ( ) н (a р (t ), e j ( ), P, P );

н (2.25) 0н н y L ( ) (a( ), e ( )), н н a р (t ) j, a( ) j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 P0 1;

0 Pн 1.

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

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

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


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

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

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

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

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

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

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

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

Классификация абстрактных вероятностных и нечетких автоматов Абстрактный многофункциональный недетерминированный автомат 3-рода Абстрактный Абстрактный Абстрактный вероятностный вероятностный нечеткий автомат 3-рода автомат 3-рода автомат 3-рода первого типа второго типа Рис. 2.15. Классификация абстрактных недетерминированных автоматов 3-го рода третьего рода представлена на рис. 2.15.

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

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

2.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-го рода использовать для определения вы ходных сигналов катастрофических отказов первого типа, когда у4(t) = 4(хр(t), aр(t)), и использовать для определения выходных сигналов катастрофических отказов второго типа выходной сигнал вероятностного автомата 3-го рода ув1() = 3(aр(), е()). Выходной сигнал у4(t) автомата 4-го рода отличается от выходного сигнала у1(t) автомата 1-го рода тем, что использует в функции выходов не состояние a(-1), а состояние aр(t), которое установлено устанав ливающим хр(t) входным сигналом. Таким образом, автомат, использующий выходной сигнал у4(t) можно назвать автоматом четвертого рода в связи с тем, что все автоматы определяются по своим выходным сигналам. На самом деле, выходной сигнал у4(t) может дополнительно добавляться в выходных сигналов любых автоматов с памятью на базовых схемах памяти. Выходной сигнал ув3() автомата 3-го рода появляется после вероятностного перехода схемы памяти в одно из запоминаемых состояний базовой схемы памяти при воздействии сохраняющего е() входного сигнала.

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

xP е y4 yв АВТОМАТ ЧЕТВЕРТОГО РОДА Рис. 2.16. Структурная схема автомата 4-го рода Таким образом, кратко рассмотрены монофункциональные 1-го и 2-го рода и многофункциональные абстрактные автоматы 1-го, 2-го и 3-го рода и предложен для использования в каждом из этих автоматов устанавливающий хр(t) входной сигнал для определения катастрофических отказов в схемах па мяти этих автоматов. Конечно, выявление катастрофического отказа в схемах памяти не решает всех проблем по проверке работоспособности схем памяти, но помогает выявлению наиболее существенных отказов - катастрофических, при которых схема памяти работать как запоминающее устройство уже не в состоянии.

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

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

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

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

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

3. СПОСОБЫ ЗАДАНИЯ АВТОМАТОВ 3.1. Некоторые понятия в теории абстрактных автоматов В литературе по классическим автоматам [12–14;

18–19;

21;

24;

26;

32;

90;

125;

140] даны некоторые важные понятия о взаимоотношениях между автоматами, такие, как: эквивалентность между автоматами, изоморфизм абстрактных автоматов, взаимоотношения между автоматами первого (Ми ли) и второго (Мура) рода.

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

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

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

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

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

3.2. Табличные и графические способы задания классических автоматов Мили и Мура Задание классического монофункционального абстрактного автомата А сводится к заданию функций переходов и функций выходов. Из сообра жений практики остановимся более подробно на способах задания автоматов с помощью таблиц и графов. Обычно для автоматов Мили функции перехо дов и выходов (2.3) задаются соответствующими таблицами с двумя входа ми. Столбик таблицы переходов 3.1 и таблицы выходов 3.2 обозначает со стояние автомата аi (аi Q), а строка – входной сигнал хk (хk Х).

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

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

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

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

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

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

х2, у х1, у а1 а х2 х1 х у4 у1 у х х1, у4 у а а х2, у Рис. 3.1. Направленный граф автомата Мили х у у х а1 а х2 х1 х х х а а у4 у х Рис. 3.2. Направленный граф автомата Мура 3.3. Табличные способы задания многофункциональных абстрактных детерминированных автоматов Задание многофункциональных абстрактных автоматов 1-го, 2-го и 3-го рода сводится к заданию соответствующих однозначной функций переходов o, функций выходов 1, 2, 3, функцией сохранения состояний e и функции укрупненных переходов y. Остановимся более подробно на способах зада ния автоматов с помощью таблиц и графов.

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

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

Таблица переходов 3.4 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi х1 а1 а2 а1 а0 х1 a4 a0 a6 a х2 а2 а3 а0 а2 х2 a5 a6 a4 a Таблица выходов 3.6 Таблица выходов 3. 1 : Q(-1) X(t) YI(t) 1 : Q(-1) X(t)YI(t) 1 а0 а4 а5 а а0 а1 а2 а3 хi хi х1 у5 у5 у6 у х1 у1 у2 у3 у х2 у6 у7 у5 у х2 у2 у1 у4 у Строки таблицы сохранения состояний (табл. 3.8) соответствуют сохра няющим е() входным сигналам, а столбцы – а() состояниям автомата. В каждой строке на пересечении со столбцами в таблице сохранения состоя ний ставится соответствующее состояние а()= е(а(t), е()), где а j, а(t) = =а() (j Q), сохраняемое под воздействием сохраняющего е() входного сигнала во время внутреннего такта автоматного непрерывного времени Т, а в остальных случаях ставятся прочерки.

Таблица сохранения состояний 3.8.



Pages:     | 1 || 3 | 4 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.