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

3.2. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ КОНЕЧНОГО АВТОМАТА

Конечным автоматом М (математической моделью реального автомата, обладающего различной физической природой) называется набор из пяти объектов [2,4]

M={X,S,Y,(p,v} ,

где Х={хо,х},...,хп} -входной алфавит (конечный набор входных

символов (букв); S = {s0, s],..., Sk} - множество внутренних состояний; Y = (Уо, Уь---,Ут} - выходной алфавит (конечный набор выходных

символов (букв); q>: S*X-> S - функция переходов ( в следующее состояние); v: S*X- Y - функция выходов.

Тем самым конечный автомат математически описывается тремя множествами X, S, Y и двумя функциями (p,v. Действие его состоит в том, что он воспринимает последовательность входных переменных (символов или букв алфавита X) и затем формирует последовательность выходных символов (букв алфавита Y). Причем работа конечного автомата происходит последовательно.

Предположим, что конечный автомат М в начале своей работы находится во внутреннем состоянии s(h), при действии на его входе символа x(h) функция выходов на паре (x(h), s(h)) принимает значение v(x(h), s(h}), что обеспечивает выдачу на выходе автоматам символаy(h), т.е.

y(h)=v(x(h),s(h)) .

Затем на этой же паре (x(h), s(h)) функция переходов принимает значение \\f(x(h), s(h)), которое является следующим внутренним состоянием автоматам, т.е.

s(h + l) = y/(x(h),s(h)) .

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

x(hl

s(h)

Комбинационная схема

xfh)

sfh + 1)

Таким образом, в общем случае конечный автомат может быть представлен в виде структурной схемы, изображенной на рис.3.1. Комбинационная схема реализует функции выходов v и переходов у/, а память сохраняет на один такт h (т.е. время At) предыдущее состояние s(h) конечного автомата М.

Конечные последовательности символов из алфавитов X, Y, S называются соответственно входными, выходными словами и словами состояний.

Если на вход автомата М поступает слово ап длиной п, то оно перерабатывается в выходное слово y(s, ап) и слово состояний s(s, ап), т.е.

y(s,a„) = v(s,X)v(s,al)v(s,a1,a2)...v(s,a1,a2,...,an) ,

Память

Рис.3.1.

Структурная схема конечного автомата

s(s,an) = у/(s,Л)у/(s,al)у/(s,a1,a2)...\f/(s,a1,a2,...,an) ,

где к - пустое слово.

Итак, функционированием конечного автомата называется тернарное отношение на множестве X *S *7 ;

F = {an,y(s,an),S(s,an)}:an eX*,seS, п = 1,2,3...4}

Отношение (3.4) показывает, как автомат, находясь в начальном состоянии s, перерабатывает входные слова ап в выходные слова y(s, ап) и слова состояний s(s, ап).

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

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

другую.

3.3. ТАБЛИЧНЫЕ СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА

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

Элементы множеств X, S, Y часто нумеруют порядковыми числами, начиная с нуля, например :

X = {0,1,2,3} , S = {0,1,2,3} , Y={0,1} ,

обозначают символами соответствующих алфавитов :

S = {sg, Sj, s3, s4} , У={Уо,У>}

или используют смешанное обозначение.

Функции выходов v и переходов \/ можно представить двумя таблицами, строки которых соответствуют состояниям, а столбцы входам автомата. Первая таблица называется таблицей переходов и соответствует функции переходов \\f(x(h), s(h)=s(h+l), ее клетки заполняются обозначениями состояний s(h+l), в которые переходит автомат при воздействии x(h), и состояний s(h) в данный тактовый момент. Вторая таблица называется таблицей выходов и соответствует функции выходов v(x(h), s(h)=y(h), ее клетки заполняются обозначениями выходов y(h) в данный тактовый момент, которые соответствуют воздействию x(h) и состоянию s(h) вэтотжемомент.

В качестве примера рассмотрим составление таблиц переходов и выходов для автомата М, представляющего собой автоматическую револьверную головку токарного станка с УЧПУ [5]. Револьверная головка имеет четыре положения, каждое из которых может устанавливаться в рабочее положение путем поворота блока резцедержателей на четверть оборота по часовой стрелке. Таким образом, установка рабочего положения происходит последовательным перемещением из одного в другое положение револьверной головки, происходящим в одном направлении. Обозначив положение s0,s1,s2,s3, отметим, что переход из положения в положение возможен лишь в сторону увеличения их индексов с переходом старшего на