Математические и логические основы электронно-вычислительной техники;

Лекция №1.

Определение автомата, способы задания автоматов.

Цели- задачи лекции:

Знать:

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

Уметь:

Представлять автоматы различными способами.

План лекции:

Понятие автомата.

Автомат Мили.

Способы описания конечных автоматов.

Стандартные или автоматные языки описания.

3.2 Начальные языки.

Примеры.

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

Цель дисциплины — представление концепции конечного автомата, который является простейшей моделью вычислительного устройства. Хотя теория конечных авто­матов изучает очень простые модели, она является фундаментом большого числа разнообразных приложений. Эти приложения — от языковых процессоров до си­стем управления реального времени и протоколов связи — покрывают значитель­ную долю систем, разработкой, реализацией и анализом которых занимается ин­форматика.

В результате изучения материала вы должны усвоить:

- общее представление о конечно автоматных преобразователях информации и
их свойствах, методах их задания, особенностях двух основных типов конечно­
автоматных преобразователей: автоматах Мили и Мура;

- проблемы минимизации и проверки эквивалентности конечных автоматов;

- методы реализации конечно автоматных преобразователей;

- примеры применения КА в различных областях и методы графического формализма конечно автоматного представления систем обработки информации;

- автоматные модели параллельных процессов.

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

Электронная техника;

математические и логические основы электронно-вычислительной техники;

цифровая схемотехника.

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

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

Число возможных входных историй бесконечно, даже если различных элементов входной информации у автомата конечное число (как в конечном функ­циональном преобразователе). Если автомат по-разному будет себя вести для каж­дой возможной предыстории, то такой «бесконечный» автомат должен иметь бес­конечный ресурс — память, чтобы все эти предыстории как-то запоминать. Введем на множестве предыстории отношение эквивалентности. Две предыстории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автомат дол­жен не обязательно запоминать входные истории, достаточно, чтобы автомат за­поминал класс эквивалентности, к которому принадлежит данная история.

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

(Внутренним) состоянием автомата назовем класс эквивалент­ности его входных историй.

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

Поскольку состояние представляет собой класс эквивалентных предыстории вхо­дов, состояние может измениться только при приходе очередного входного сигна­ла. При получении входного сигнала конечный автомат не только выдает инфор­мацию на выход как функцию этого входного сигнала и текущего состояния, по и меняет свое состояние, поскольку входной сигнал изменяет предысторию. Функ­ционирование автомата удобно представлять графически. На рис. 1 блок памяти автомата хранит информацию о текущем состоянии S, которое вместе с входным сигналом X определяет выходную реакцию автомата У и следующее состояние S'.

Рис. 1. Автоматный преобразователь и его реализация.

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

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

Рис. 2

Множества дискретных воздействий, реакций и состояний представляются в теории абстрактных автоматов с помощью соответствующих алфавитов. Поэтому введем в рассмотрение алфавит (множество) входных сигналов V={v}, алфавит (множество) выходных символов W={w}, а также алфавит (множество) состояний автомата S={s}. Каждый входной символ vÎV отображает входное воздействие, а выходной символ wÎW реакцию автомата.

Предполагается, что множества V и W конечны. Если множество S конечно, то автомат называется конечным (finite automatum), а если S бесконечно, то автомат называется автоматом с бесконечным числом состояний. Если автомат имеет всего лишь одно состояние, то он называется тривиальным, или автоматом без памяти.

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

Получая на входе последовательность (цепочку) входных символов v(0)v(1)v(2)… автомат вырабатывает последовательность (цепочку) выходных символов w(0)w(1)w(1)… . Функциональная зависимость выходной последовательности символов от входной последовательности автомата называется алфавитным оператором, реализуемым данным автоматом.

Алфавитный оператор автомата теоретически можно определить следующим образом

w(t)= l_v[v(0)v(1)v(2)…v(t)], (1)

где l_v[×]- функция от цепочки t+1 входных символов. Функция l_v[×] дает значение выходного символа w(t) в момент времени t в зависимости от последовательности v(0)v(1)v(2)…v(t) символов, поступивших к этому моменту на входе автомата. Однако, практическое использование определения (1) в общем случае нереально, хотя бы потому, что автоматное время t может принимать сколь угодно большое значение, и, следовательно, потребовалось бы описать реакцию автомата для бесконечного множества входных последовательностей v(0)v(1)v(2)…v(t) при t®¥.

На практике поступают следующим образом. Бесконечное множество входных последовательностей разбивается на классы (события) таким образом, что каждому классу соответствует некоторое состояние sÎS автомата, а именно, множество {v(0)v(1)v(2)…v(k)}_s входных последовательностей, приводящих автомат в некоторое состояние sÎS. Таким образом, состояние s можно рассматривать в качестве представителя множества {v(0)v(1)v(2)…v(k)}_s. Отметим, что в множество {v(0)v(1)v(2)…v(k)}_s для конкретного s могут входить цепочки v(0)v(1)v(2)…v(k) самой разной длины.

Итак, автомат может находиться в одном из множества S состояний. Если в момент времени t автомат находится в состоянии s(t) и на вход его поступает символ v(t) ÎV, то в следующий момент времени t+1 автомат переходит в состояние s(t+1) в соответствии с функцией переходов

s(t+1)=l[s(t),v(t)]. (2)

Функция переходов l[×,×] реализует отображение некоторого подмножества множества D_l ÍS´V декартова произведения S´V в множество S. Если задано состояние автомата s(0)ÎS в начальный момент t=0, то состояние его s(t+1) в момент t+1 является отображением входной последовательности v(0)v(1)…v(t). Функция переходов l[s(t),v(t)] представляет это отображение как функцию двух аргументов: состояния s(t), представляющего цепочку v(0)v(1)…v(t-1), и входного символа v(t).

Автомат Мили

Выходной символ автомата Мили в момент времени t определяется функцией выходов

w(t)=m[s(t),v(t)]. (3)

Таким образом, функция выходов автомата Мили реализует отображение некоторого подмножества D_m ÍS´V декартова произведения S´V в множество W.

Напомним, что декартово произведение множества A и B, обозначаемое AxB, есть множество .

Иногда, для краткости используют обозначение: s⁺=s(t+1), s=s(t), v=v(t), w=w(t). Тогда функция переходов автомата Мили запишется в виде s⁺=l(s,v), а функция выходов в виде w=m(s,v).

Автомат называется полностью определенным, если D_l=D_m=S´V. В противном случае автомат называется частичным. Иными словами, у полностью определенного автомата области определения функций l[×,×] и m [×,×] совпадают с декартовым произведением S´V, а у частичного автомата эти функции определены на подмножествах D_l и D_m множества S´V.

Способность автомата фиксировать состояния, представляющие классы входных последовательностей (события), называют памятью автомата. Каждое состояние sÎS автомата представляет некоторый класс эквивалентности {v(0)v(1)v(2)…v(k)}_s входных последовательностей, поскольку поведение автомата в любой момент времени t зависит только от класса, т.е. s(t), и входного воздействия v(t). Такой подход позволяет устранить время как явную переменную и выразить выходные символы как функцию состояний и входных символов в данный момент времени, что находит выражение в общей записи модели A абстрактного автомата Мили:

A = <V,W,S,l,m,s(0)>, (4)

где

V,W,S - алфавиты входных, выходных символов и символов состояний соответственно;

l, m - функции переходов и выходов соответственно;

s(0) - начальное состояние.