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

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

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

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

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией
Контрольная работа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

у которого:

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

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

    λ : Х → Y – функция выходов, реализующая отображение φλ Х на Y.

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

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

А = (Х, Y, Q, δ, λ, а0),(2)

где

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

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

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

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

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

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

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

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

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

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

а(t) = δ(а(t – 1), х(t)), у1(t) = λ1(а(t – 1), х(t)), (t = 1, ...), (3)

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

а(t) = δ(а(t – 1), х(t)), у2(t) = λ2(а(t)), (t = 1, ...),(4),

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

а(t) = δ(а(t – 1), х(t)), у1(t) = λ1(а(t – 1), х(t)), у2(t) = λ2(а(t)),

(t = 1, ...), (5)

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

Рис. 2 Структурные схемы монофункциональных автоматов 1-го и 2-го рода

Построенное указанным способом искомое отображение φ, а именно: q = =φ(р), называют отображением, индуцированным абстрактным автоматом А.

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

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

Похожие работы

1 2 3 4 5 > >>