Особенности дискретных автоматов

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

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

Особенности дискретных автоматов



Содержание

1. Развитие теории автоматов

2. Понятия автомата: термины и определения

2.1 Алфавитный способ преобразования информации

2.2 Понятие об алгоритме

2.3 Понятие о дискретном автомате

Заключение

Литература



1. Развитие теории автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе булевой алгебры и модели дискретного устройства в виде так называемого конечного автомата. На ней основано развитие методов логического проектирования дискретных устройств и методов построения тестов для проверки последних, обеспечение надежности и устойчивости их работы, решения задач «конструирования» дискретных устройств. Возникли отдельные ответвления теории конечных автоматов в виде теории вероятностных и нечетких автоматов, коллективного поведения автоматов, экспериментов и т. д. [14; 18-21; 24-26; 34-35; 90; 119; 125; 140],

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

В Библии сказано, что в начале было слово… Когда-то язык был слабым преобразованием вещей в сознании человека, прозрачной зыбкой моделью, отделяющий человека от неживой материи. За прошедшие тысячелетия язык развился до такой степени, что сам проявляет тенденцию к независимому движению и управляет развитием разума. Он сконцентрировал в себе все тайны Вселенной, в нем, возможно, скрыты ответы на извечные вопросы бытия.

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

Наши модели вначале нечеткие. Это наглядно видно на примере изучения счета ребенком с 2 до 5 лет [65]. Ему необходимо повторить от 6-ти до 10 раз, чтобы он мог вначале различать один палец от двух. Наши мысли, сформированные на основе независимых моделей тоже нечеткие. Этим мы существенно отличаемся от дискретного компьютера!

Человек, помимо способности рассуждать и логически мыслить, обладает, как все живые существа, способностью принимать в расчет параллельно соображения, как общего, так и сопутствующего характера. Не рискуя сильно ошибиться, как писал французский профессор Арнольд Кофман, - «можно предсказать, что технология будет развиваться по пути, сближающем идеи компьютерного и обычного человеческого мышления в ожидании того дня, когда компьютеры начнут обрабатывать общую информацию принципиально параллельно с частной, без предварительной последовательной обработки» [49].

Понятие вероятности развивалось с XVII века. Идея вероятности появилась в процессе развития квантовых представлений в физике в начале ХХ столетия. Возник вопрос о соотношения динамических и статических законов. Известна дискуссия между Нильсом Бором и Альбертом Эйнштейном. В этой дискуссии Бор отстаивал вероятностный характер микропроцессов, а Эйнштейн отстаивал классическое представление, утверждая, что «Бог не играет в кости». К сожалению, эта дискуссия не завершилась и до сих пор.

Нобелевский лауреат, философ Илья Пригожин внес один новый и истинно важный момент в эту центральную для нас проблему, который позволяет решить вопрос о соотношении причиной детерминированности и многовариантности решений в сложных системах. Почему случайность реализуется именно так, как это происходит, а не иначе. Только ответ на данный вопрос позволяет понять, что такое условие и в чем специфика его влияния [133].

Теория автоматов возникла в середине ХХ столетия в связи с изучением свойств конечных автоматов. Исторически наиболее рано начала развиваться теория комбинационного синтеза релейно-контактных схем с использованием булевой алгебры [3-6;15; 21; 36; 87; 93].

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

В работах академика В.М. Глушкова и его школы была решена задача сопряжения этапов абстрактного и структурного синтеза и представление всей структурной теории автоматов в виде, пригодном для решения проблем синтеза цифровых автоматов с запоминающими двоичными элементами любой природы. Эта объединенная математическая теория цифровых автоматов была доведена до практического применения при разработке автоматизированной системы логического проектирования дискретных устройств [24-26]. В основу этой теории были положены автоматы Мили (автоматы 1-го рода) и Мура (автоматы 2-го рода) с памятью на двоичных триггерах [24].

В настоящее время вся теория автоматов делится на теорию абстрактных и структурных автоматов Мили и Мура, функционирующих в дискретные моменты времени t_i (i = 1, 2, 3 …,n,…).

Настоящий раздел посвящен изложению существующей классической теории автоматов Мили и Мура с памятью на двоичных триггерах и функционирующих в дискретные моменты времени t_i, выявлению их ограничений. В этом разделе также предлагается более общая теория многофункциональных автоматов Мараховского 1-го и 2-го рода, частным случаем которой являются автоматы Мили и Мура, и теория автоматов 3-го рода [55; 59; 64].

Этот материал неоднократно излагался автором и его последователями в ряде работ [70-71; 79; 83-84], в учебных пособиях при чтении обязательного раздела по теории автоматов в курсе «Компьютерная схемотехника» [54-55; 66; 74], а также частично изложен в ряде статей и патентов. А также автором была предложена теория автомата 4-го рода, решающая вопрос выявления катастрофических отказов в базовых схемах памяти, что позволяет частично контролировать работоспособность базовых схем памяти в используемых устройствах компьютерных систем.

В настоящее время широко разрабатывается теория построения реконфигурируемых систем на «автоматном» уровне. Память на триггерах, которая применяется в этих устройствах и имеет жесткую (неизменяемую) структуру, не дает возможность использовать «элементный» уровень в теории построения реконфигурируемых систем [32; 39; 42; 91; 104-106; 138; 143].

Расширенная автором теория автоматов позволила создать теорию проектирования реконфигурируемых устройств с учетом «элементного» уровня с памятью на элементарных многофункциональных и многоуровневых схемах памяти [61-63].



2. Понятия автомата: термины и определения

2.1 Алфавитный способ преобразования информации

Философы и математики, заметив одинаковые законы развития разнообразных объектов, предложили общее понятие - сложная система.

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

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

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

Существуют два различных подхода с информационной точки зрения: изучение явлений в непрерывном или дискретном времени. Характерным для непрерывного подхода являются вещественные числа, которые могут изменяться непрерывно. При дискретном подходе временные координаты принимают дискретные ряды значений. Обычно нулевой момент времени считается начальным, а остальные моменты времени в соответствии с их номерами: 1, 2, …, n,… Чаще всего ограничиваются рассмотрением конечных временных интервалов, начиная с нулевого или с первого момента времени.

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

· чувствительность воспринимающего устройства дает ему возможность различать лишь конечное число градаций значений величин, характеризующих процесс;

· разрешающая способность устройства приводит к тому, что достаточно малые участки пространства воспринимаются как отдельные точки;

· полосы пропускания воспринимающего информацию устройства не позволяют ему различать очень близкие моменты времени.

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

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

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

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

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

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

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

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

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

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

>= f()¹,(1.1)

где стрелка «>» - знак преобразования информации, то есть отображение явления в явление .

Если подобное отображение осуществляется определенным объектом, то такой объект называется преобразователем информации.

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

Первый алфавит при этом называется входным, а второй - выходным алфавитом другого оператора. В случае совпадения входного и выходного алфавита говорят, что алфавитный оператор задан в соответствующем алфавите.

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

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

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

Большое значение имеет кодирующее отображение, которое называют просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а₁ алфавита А некоторой конечной последовательности в алфавите B, называемой кодом соответствующей буквы. Различным буквам алфавита А сопоставляются различные коды. Кодирующее отображение должно быть обратимым, то есть взаимная однозначность соответствующего кодирующего отображения. Обратимость кодирования будет всегда выполняться, если соблюдаются следующие два условия:

1. коды различных букв исходного алфавита А различны;

2. код любой буквы алфавита А не может совпадать ни с каким из отрезков кодов других букв алфавита В. С помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в стандартном двоичном алфавите, содержащим две цифры (буквы) 0 и 1. Двоичное кодирование должно соблюдаться при выполнении следующего соотношения:

2^m ? n,(1.2)

дискретный автомат кодирование алфавит

где n - число различных букв исходного алфавита А;

m - количество цифр двоичного алфавита, необходимых для кодирования букв алфавита А.

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

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

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

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

2.2 Понятие об алгоритме

Понятие алгоритма является одним из фундаментальных понятий современной математики. Известно, что слово алгоритм пришло из Персии. Предложил его автор книги c математики Abu Jafer Mohammed ibn Musa al Khowarizmi. Он определил его как определенный специальный метод разрешения поставленной проблемы.

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

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

Потребности человечества в обобщении многочисленных подходов к решению разнообразных задач привели к созданию теории алгоритмов.

Понятие алгоритма является одним из фундаментальных понятий современной математики. В математической теории алгоритмов существует большое разнообразие определений алгоритма, которые ориентированы на различные способы вычислительной реализации. Например, арифметическое исчисление предикатов (К. Гедель, 1931), л-определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936 и А. Тьюринг, 1937), алгоритмы Маркова (А. А. Марков, 1951) и многих других видных ученых. Попытку описать общую теорию алгоритмов предпринял В. М. Глушков в книге «Теория алгоритмов» [25], в которой он с системных позиций описал абстрактную теорию алгоритмов и связал ее с компьютерами, автоматами и самосовершенствующимися системами.

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

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

Алгоритмы могут быть однозначные, вероятностные, нечеткие, самосовершенствующиеся и т. д.

Примером однозначного алгоритма может быть система правил сложения целых чисел в произвольной позиционной системе счисления (двоичной, восьмеричной, десятичной и т. д.), которая состоит из правил поразрядного сложения и определения поразрядного переноса в старший разряд. Этот алгоритм сложения чисел С = А + В можно задать в формульном виде так [65]:

(1.3)

где с_і -- цифра і-го разряда результата;

р_і+1 -- перенос в і+1 разряд;

q - основание системы счисления.

Этот алгоритм перерабатывает слова а+b в алфавите, состоящим из q цифр и знака сложения, в слова в том же алфавите, но без знака суммы (+). Примером вероятностного алгоритма могут быть различные игры (в кости, в шашки, в шахматы и т. д.). Применительно к вероятностным алгоритмам выбор «лучшего» хода определяется не однозначно, а случайно, в соответствии с какими-либо вероятностными критериями.

Игру в шахматы можно трактовать как преобразование слов в конечном алфавите. В качестве алфавита здесь применяются символы шахматной нотации. Словами считают конечные последовательности букв алфавита. Одни последовательности представляют собою шахматные позиции, а другие - бессмысленные наборы символов, как например, 3КЛad. Алгоритм задается лишь для слов, представляющих осмысленные позиции в позицию, возникающую из нее после выполнения очередного хода. Опыт игры в шахматы показывает, что можно составить конечную систему стратегических правил, позволяющих в каждой конкретной ситуации выбрать единственный наилучший (в некотором смысле) ход. Присоединяя эту систему стратегических правил к правилам движения фигур, получаем алгоритм, который, несмотря на свою неоднозначность, можно назвать алгоритмом шахматной игры. Разработанный машинный алгоритм шахматной игры позволил компьютеру выиграть у чемпиона мира Каспарова [47].

Нечеткие (размытые, расплывчатые или неопределенные) алгоритмы, допускающие использования нечетких инструкций, широко распространены в различных сферах человеческой деятельности. Они позволяют описывать приближенные рассуждения и, следовательно, являются полезным инструментом для приближенного анализа таких систем и процессов принятия решений, которые слишком сложны для применения общепринятых количественных методов [34-35; 49].

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

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

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

Одно из важнейших фундаментальных понятий теории алгоритмов является рекурсия. Под рекурсией в общем смысле понимают такой способ организации системы, при котором она в отдельные моменты своего развития, определяемые ее правилами, может создавать (вызывать) собственные изменения копий, взаимодействовать с ними и включать их в свою структуру. Законы изменения копий при вызове также включаются в правила системы и могут зависеть от многих параметров: от состояния системы и других подсистем в момент вызова копии, от информационного наполнения заданных параметров, от правил самой системы. Частным случаем является чистая рекурсия, в которой отсутствуют изменения при вызове копии. Существует многообразие вариантов поведений копий. Они могут существовать и развиваться параллельно с главной системой, исчезать после своего этапа функционирования, по-разному взаимодействовать между собой. Все определяется правилами системы. В теории алгоритмов доказано, что, используя рекурсию, можно из ограниченного количества функциональных единиц получить все многообразие вычислительных функций [10].

При организации цикличных процессов используются рекурсивные выражения, которые описывают любой член последовательности чисел. Таким примером могут быть числа Фибоначчи, где первые два члена равны 1, а остальные вычисляются с помощью формулы a_i = a_i-2 + a_i-1. Такая формула называется рекурсивною. Входными данными для каждого последующего шага являются результаты предыдущего [128; 130].

Структурная блок схема алгоритма определения ряда чисел Фибоначчи, чтобы последнее число не превышало 100, представляет вычислительный рекурсивный процесс с неизвестным числом повторений (рис. 1.1).

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

Алгоритмы А.А. Маркова, называемые также нормальными алгоритмами, преобразуют слова, заданные в любом конечном алфавите А = А(а₁, …, a_n), в слова в том же самом алфавите, причем, как правило, алгоритм оказывается определенным лишь для части слов и задает, следовательно, частичное отображение.

Рис. 1.1. Определение чисел Фибоначчи



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

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

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

В данной работе основное внимание будет уделяться цифровым автоматам (компьютерам), которые функционируют в автоматном времени. Начиная с 40-х годов ХХ столетия, вся цифровая вычислительная техника проектировалась в целом с использованием классической теории автоматов Мили и Мура, память в которых использовалась в основном на триггерах (элементарных монофункциональных схемах памяти с закрытой структурой и с «нулевой» избыточностью). Все существующие машинные алгоритмы в той или другой мере использовали только один однозначный тип перехода в автоматах Мили и Мура - детерминированный переход за один машинный такт из одного состояния в другое, который зависел от предыдущего состояния автомата а(t_i-1) и входного сигнала х(t_i) в дискретный момент времени t_i. Это обстоятельство определило последовательность работы машинных алгоритмов. Для параллельных алгоритмов необходимо было использовать аналогичную дополнительную аппаратуру. Примером может служить использования не менее двух сопроцессоров в компьютере и т. д.

С появлением многофункциональных автоматов Мараховского на схемах автоматной памяти [55; 58-64; 66-67; 70-85], возможности теории алгоритмов расширились в связи с качественно новыми дополнительными переходами в устройствах компьютера (hardware) [59]. Автоматная схема памяти, используя меньшее количество аппаратуры на одно запоминаемое состояние по сравнению с триггерами, в тоже время, оказалась в состоянии осуществлять качественно новые переходы в автоматах.

Автоматная схема памяти способна еще выполнять качественно новые переходы, такие как [64]:

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

2. вероятностный переход в одно из подмножеств автомата, которые сохраняются под влиянием входных сигналов е;

3. нечеткий переход в одно из четких подмножеств автомата, которое входит в нечеткое множество.

Появление возможности осуществлять качественно новые переходы в схемах памяти позволило Мараховскому и его ученикам расширить теорию автоматов [56-64; 66-85]. Авторы надеются, что это обогатить в дальнейшем и теорию компьютерных алгоритмов, и теорию построения устройств компьютеров, а также сможет явиться элементной базой для построения реконфигурируемых устройств, которой недостает в современных работах по когнитивному направлению при создании модели человеческого мозга [1-2; 101].

Подводя итоги можно сказать, что рассмотрение многофункциональных автоматов, предложенных Мараховским [55], функционирование которых рассматривается в непрерывное автоматное время, расширяет теорию классических автоматов Мили и Мура и создает в ней новое направление, позволяющее описывать устройства на схемах автоматной памяти, создавать качественно новые вычислительные алгоритмы. Построение многоуровневых схем памяти на основе многофункциональных автоматов, которые не только изменяют структуру запоминания состояний, но и определяют направление запоминаемой информации для образования связей с новыми схемами памяти, необходимых для создания нейронных сетей [1-2; 92; 96; 101].

2.3 Понятие о дискретном автомате

Дискретными автоматами Мили и Мура называют устройства преобразующие информацию в дискретные моменты времени, которые в математике отождествляются как точка на числовой оси (рис. 1.2, а) t_i (i = 0, 1, 2, …, n, …), а в реальном устройстве как такт t (рис. 1.2, б).

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



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

Второе допущение состоит в том, что переход в следующее состояние оказывается возможным после переходного процесса в схемах памяти автомата, которые имеют разброс параметров, но для данного автомата составляет некоторый фиксированный промежуток времени, который обычно выбирается равным четырем задержкам ф_э элемента. Такой интервал дискретности автомата обычно выбирается как такт t машинного такта Т (рис. 1.2. б.). Промежуток между тактами t в теории автоматов принято называть пустым словом е нулевой длины, т. к. под воздействием слова е автомат не способен переходить из одного состояния в другое, а только^, выполняет функцию д_e сохранения установленного состояния [64]. Такое допущение дает возможность рассматривать функционирование цифрового автомата Мили или Мура в дискретном автоматном времени t_i (рис. 1.2, б). При построении такого дискретного автоматного времени различают два основных случая:

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

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

Теория асинхронных автоматов существенно отличается от теории синхронных автоматов тем, что в ней рассматриваются не только моменты фактически имевших место переходов, но также и такие переходы, которые в данный момент возможны, но не произошли переходы. К числу таких моментов причисляют моменты прихода входных сигналов х(t) импульсного типа (мгновенных) и изменения уровня напряжения сигналов потенциального типа, действующих во временном интервале такта t (рис. 1.2, б). При этом считают, что интервал дискретности автомата ограничивает минимально возможное расстояние между дополнительно вводимыми моментами автоматного времени. При таком допущении теория асинхронных автоматов в ряде случаев может быть сведена к синхронному случаю, поскольку фактически длины интервалов между последовательными моментами дискретного автоматного времени в идеализированной теории автоматов (без учета переходных процессов) не имеет никакого значения, так как на автомат в этот момент поступает пустое слово е нулевой длины. Имея в виду такое обстоятельство, в функционировании автоматов Мили и Мура используется абстрактное дискретное автоматное время, принимающее целые неотрицательные значения: t = 0, 1, 2, …, n, …, и строится теория, как теория последовательных синхронных автоматов, хотя в действительности она охватывает в значительной мере и теорию асинхронных автоматов.

Переходы из одного а_i состояния автомата в другое a_k вызываются входными сигналами x(t), возникающими вне автомата и передающимися в автомат по конечному числу входных каналов. В отношении х(t) входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных х(t) входных сигналов обязательно конечно, а, во-вторых, х(t) входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами. Особо следует подчеркнуть, что реальный физический входной сигнал, вызывающий изменения состояния автомата в момент времени t_i, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к моменту времени t_i, а не t_i-1.

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

В многофункциональных автоматах Мараховского, которые названы по фамилии предложившего их автора, используется автоматная память [61--63], вводится и используется автоматное непрерывное время. В автоматном непрерывном времени кроме такта t_i используется еще промежуток между тактами t_i, интервал которого обозначим символом «». Это объясняется тем, что в интервале используется сохраняющий входной сигнал е(), который в автоматах Мили и Мура называется пустым словом нулевой длины и не учитывается при синтезе автоматов, а в многофункциональных автоматах может использоваться для осуществления укрупненных переходов в автоматной памяти автомата.

Рассмотрим автоматное непрерывное время с учетом синхронных сигналов ф_j и дадим ряд определений. Определение 1.1. Тактом назовем промежуток времени, на протяжении которого на автомат можно подавать произвольный синхронизирующий сигнал ф_i. Определение 1.2. Внутренним тактом назовем меньший открытый промежуток времени между появлениями синхронизирующих сигналов ф_i.

Определение 1.3. Внешним тактом назовем меньший открытый справа промежуток времени, который соответствует периоду синхронизированного сигнала ф_i.

Такты, что определены, можно выразить такой формулой:

(1.4)

Информационные входные сигналы х(t) подаются на входные каналы сложного автомата и синхронизируются сигналом ф_j. Эти входные сигналы воздействуют на автомат в автоматное непрерывное время такта .

Определение 1.4. Внутренним единичным тактом Д₀ автоматного непрерывного времени назовем меньший открытый промежуток времени между появлением двух произвольных и последовательных синхронизированных сигналов ф_р и ф_{р + 1}.

Определение 1.5. Внешним единичным тактом Т₀ назовем меньший открытый справа промежуток времени, который соответствует периоду времени между появлением двух произвольных и последовательных синхронизирующих сигналов ф_р и ф_{р + 1}.

Внешний единичный такт Т₀ в соответствии со временем равен сумме продолжительности такта и внутреннего единичного такту Д₀. Эта зависимость рассматривается таким равенством:



Т₀= + Д₀.(1.5)

Продолжительность внешнего такта равна продолжительности внешнего такта Т_а автомата. За один внешний такт Т_а на автомат воздействуют все синхронизирующие сигналы ф_j по одному разу.

Определение 1.6. Внешним тактом Т_а автомата назовем меньший открытый справа промежуток времени, который соответствует периоду воздействия всех синхронизирующих сигналов ф_j (j = 1, 2 ,…, C) на входных каналах автомата.

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

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

Под влиянием входного сигнала x(t) во время такта элементарный автомат с памятью может переходить в определенное состояние при реализации однозначного перехода. Под воздействием входного сигнала е(Д) во время внутреннего единичного такта Д₀ элементарный многофункциональный автомат с памятью может переходить в новое состояние при реализации функции укрупненного, вероятностного или нечеткого перехода.

Новое установленное состояние элементарного автомата может сохраняться после окончания такта при однозначном переходе или после внутреннего единичного такта Д₀ при реализации функций укрупненного или вероятностного перехода.

Временные соотношения синхронизирующих и входных сигналов иллюстрирует рис. 1.3. Выходной сигнал у_j элементарного автомата фиксирует новое устойчивое состояние в автомате и сохраняет неизменным это состояние на всем временном отрезке . Отрезок определяется в соответствии с такой формулою:

= - Д₀. (1.6)

Внешний такт Т_а автомата своею продолжительностью равный сумме внешних единичных тактов Т₀:

(1.7)

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

В автоматах Мили, рассматриваемых в автоматном дискретном времени, выходной сигнал у¹(t) определяется парой (х(t), а(t-1)), а сам автомат называется автоматом первого рода.



В автоматах Мура, рассматриваемых в автоматном дискретном времени, сдвинутый выходной сигнал у²(Т) определяется парой одинаковых состояний а(t) и а(Д), где Т = t + Д. Состояние а(t) устанавливается только после перехода автомата в это состояние под воздействием х(t) входного сигнала. Состояние а(Д) сохраняется при сохраняющем е(Д) входном сигнале. Сам автомат называется автоматом второго рода.

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

Схемы автоматной памяти представляют собою матрицу запоминаемых состояний [64], состоящую из блоков р_j, представляющих строки матрицы, в которых сохраняются подмножества определенных состояний автоматной схемы памяти под влиянием входного сигнала е(Д), и блоков µ_і, представляющие столбцы матрицы с определенными подмножествами состояний автоматной схемы памяти, устанавливаемых входным сигналом х(t).

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

В детерминированных автоматах Мараховского дополнительно рассматривается функция д_е сохранения состояний а(Д), которая определяется парой (а(t), е(Д)). Входной сигнал е(Д) сохраняет состояние а(t) автоматов 1-го и 2-го рода после его установки на всем протяжении машинного такта Т в определенном подмножестве р_j (рис. 1.3). Функции переходов из одного состояния а(Д-1) в другое состояние а(t) определяется парой (а(Д-1), х(t)), а сохранение состояния а(Д) во время промежутка Д определяется парой (а(t), е(Д)).

В автоматах 3-го рода функция укрупненного перехода из состояния а(t) в состояние а(Д) осуществляется под воздействием входного сигнала е(Д) в определенном подмножестве µ_i и определяется парою (а(t), е(Д)).

Типы выходных сигналов у определяют род автомата. Выходной сигнал у¹ автомата первого рода определяется парой (а(Д-1), х(t)), выходной сигнал у² автомата второго рода определяется парой (а(t), а(Д)), а выходной сигнал у³ автомата третьего рода определяется парой (а(t), е(Д)). Общая теория автоматов при описанных допущениях разбита на абстрактную теорию автоматов и структурную теорию автоматов. В абстрактной теории автоматов отвлекаются от структуры самого автомата и его входных и выходных сигналов. Входные и выходные сигналы рассматриваются как буквы двух фиксированных алфавитов - входного и выходного. Абстрактная теория изучает лишь те переходы, которые осуществляет автомат под воздействием входных сигналов, и те выходные сигналы, которые выдаются.

Абстрактная теория автоматов, таким образом, близка к теории алгоритмов, являясь по существу ее дальнейшей детализацией.

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

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

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

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

Один тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(Д-1) подмножества р_i в состояние а(Д) подмножества р_k (р_i ? р_k) с определенной вероятностью Р₁ под влиянием пары (х_р(t). e_k(Д)), в которой входной сигнал х_р(t) устанавливает в схеме памяти не запоминаемое состояние а_р(t) ни при одном входном сигнале e(Д). Другой тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(Д-1) подмножества р_i в состояние а(Д) подмножества р_k (р_i ? р_k) под влиянием пары (х(t). е^в(Д)), в которой входной сигнал е^в(Д) с определенной вероятностью Р₂ определяет подмножество сохраняемых состояний р_k. Вероятностный переход второго типа возможен при рассмотрении трех уровней автоматной схемы памяти в цифровом автомате.

Нечеткие переходы в нечеткие подмножества Q_н, состоящие из определенного числа четких подмножеств р_i, определяют переходы из вполне определенного состояния автомата а(Д-1) подмножества р_i в состояние а(Д) подмножества р_k (р_i ? р_k) с определенной вероятностью Р_н под влиянием пары (х_р(t). е^в(Д)).

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



Заключение

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



Литература

Пухальский Г.И., Новоселова Т.Я. Цифровые устройства. Учебное пособие для вузов. - Санкт-Петербург: Политехника издательство, 2006. - 880с.

Захаров Н.Г., Рогов В.Н. Синтез цифровых автоматов: Учебное пособие - Ульяновск: УлГТУ, 2013. - 136с.

В.А.Горбатов, А.В.Горбатов, М.В.Горбатова Теория автоматов: Учебник для студентов втузов. - М.: АСТ: Астрель. - 559с.

Ю.Г.Карпов Теория автоматов: Учебник для вузов. - 1-е издание. - СПб: Издат. дом ПИТЕР, 2013 год. - 208с.

Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов - М.: Высшая школа, 1987, - 272с.

Брауэр В. Введение в теорию конечных автоматов. Перевод с английского под редакцией Ю.И. Журавлева-М. Радио и связь, 1987, - 392с.

Глушков В.М. Синтез цифровых автоматов, Государственное издательство физико-математической литературы. Москва 1962.

Каган Б.М. Электронные вычислительные машины и системы.- М. Энергоавтомиздат, 1988, - 551с.

Киносита К., Асада К., Карашу О. Логическое проектирование СБИС - М. Мир, 1988, - 309с.

Савельев Н.В., Коняхин В.В. Функционально-логическое проектирование БИС.-М. Высшая школа, 2000. - 156с.

А.Фридман, П.Менон. Теория и проектирование переключательных схем. Москва. Мир. 1978

С.З.Кузьмин. Основы теории цифровой обработки радиолокационной информации. Москва. Советское радио. 1974

Д.А.Поспелов. Логические методы анализа и синтеза схем. Москва. Энергия. Издание третье, переработанное и дополненное. 1974.

Киносита К., Асада К., Карашу О. Логическое проектирование СБИС - М. Мир, 1988, - 309с.

Шило В.Л. Популярные цифровые микросхемы. Справочник. - Челябинск: Металлургия, 1988.

Браммер Ю.А., Пащук И.Н. Импульсные и цифровые устройства. - М.: Высшая школа, 2013.

Размещено на Allbest.ru