|
134 Конечный автомат можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом, или алфавитом состояний); начальным состоянием zo, zqgZ\ функцией переходов (p(z,x)\ функцией выходов y/(z,x). Автомат, задаваемый F-схемой: F= примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие /-му такту при * t=0,1,2,...., через z(t),x(t),y(t). При этом по условию, z(0)= zo, a z(t)eZ, x(t) еХ, y(t) eY Конечный автомат имеет один входной и один выходной каналы. В каждый момент t=0,1,2,... дискретного времени, F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени /=0 он всегда находится в начальном состоянии z(0)=zo. В момент /, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(t) еХ и выдать на выходном канале сигнал y(t)=y/[z(t),x(t)], переходя в состояние z(t+ l)(p[z(t),x(t)], z(t) eZ, y(t) eY. Конечный автомат реализует некоторое отображение мно-ф жества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние zo, подавать в некоторой последовательности буквы входного алфавита х(0),х(1),х(2) , ..., т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у(0),у(1),у(2), ..., образуя выходное слово. |
d у d у d x d x <*o — +«i + ...+d„y=b0 +Z>! + ...+b„x. (2.12) , n , n l ,m jffi-1 dt dt dt dt В уравнении (2.12) для простоты предполагается, что точки приложения возмущающих воздействий совпадают с входом системы. Для решения (2.12) можно воспользоваться, например, операторным методом, заменяя дифференциальное уравнение алгебраическим. Таким образом, использование D-схем позволяет формализовать процесс функционирования непрерывно-детерминированных систем S и оценить их основные характеристики, применяя аналитический или имитационный подход, реализованный в виде соответствующего языка для моделирования непрерывных систем или использующий аналоговые и гибридные средства вычислительной техники. 2.3. ДИСКРЕТНО-ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ» (f-СХЕМЫ) Особенности дискретно-детерминированного подхода на этапе формализации процесса функционирования систем рассмотрим на примере использования в качестве математического аппарата теории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — автоматы. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Понятие «автомат» варьируется в зависимости от характера конкретно изучаемых систем, от принятого уровня абстракции й целесообразной степени общности. Основные соотношения. Автомат можно представить как некоторое устройство (черный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. Конечным автоматом называется автомат, у которого множество внутренних состояний и входных сигналов (а следовательно, и множество выходных сигналов) являются конечными множествами. Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z0, z0eZ; функцией переходов cp(z, х); функцией выходов \j/(z, x). Автомат, задаваемый F-схемой: F—^Z, X, Y, ср, ф, z0>,— функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг 54 к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также ВХОДНОЕ и выходной сигналы, соответствующие f-му такту при t=0, 1, 2, ..., через z(t), x(i), y(t). При этом, по условию, z(0)=zo, a z(t)eZ, x(t)eX, y(t)<=Y. Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t=0, 1, 2, ... дискретного времени .F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени *=0 он всегда находится в начальном состоянии z(0)=zo. В момент t, будучи в состоянии z(j), автомат способен воспринять на входном канале сигнал x(t)eX и выдать на выходном канале сигнал у(() = ф [z (/), х (*)], переходя в состояние z (t +1)=ср [z (/), х (t)], z(t)eZ, y(f)e Y. Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z0, подавать в некоторой последовательности буквы входного алфавита х(0), JC(1), x(2),..., т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у(0), У ОХ у(2), ..., образуя выходное слово. Таким образом, работа конечного автомата происходит по следующей схеме: в каждом f-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом в (/+1)-м такте в новое состояние z(t + l) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для F-автомата первого рода, называемого также автоматом Мили, z(t+l) = е. функция выходов не зависит от входной переменной x(t), называется автоматом Мура. Таким образом, уравнения (2.13) — (2.17), полностью задающие ^-автомат, являются частным случаем уравнений (2.3) и (2.4), когда система S детерминированная и на ее единственный вход поступает дискретный сигнал X. |