Марковские процессы

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

Случайный процесс мы будем обозначать где принимают значения из некоторого множества Z, a t – моменты времени, Значение , , принимаемое процессом в момент t – состояние процесса в момент t, множество Z – пространство состояний процесса, функции z=z(t) для всех - траектории дли реализации случайного процесса .

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

Конечные автоматы.

Существет класс систем, для описания которых оказывается весьма полезной специальная математическая схема – конечные автоматы.

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

Словом в данном алфавите называется конечная упорядоченная совокупность букв. Например в алфавите (x,y) словами будут хху, хух и т д. Длина слова изменяется числом содержащихся в нем букв. Употребляется так же пустое слово, не содержащее ни одной буквы; оно обозначается пустым множеством.

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

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

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

Отображение F, индуцируемое автоматом, удовлетворяет следующим двум условиям: 1) любому входному слову ставится в соответствие выходное слово , имеющее с одинаковую длину; 2) если - начальный отрезок слова , то слово является начальным отрезком слова .

Эти условия называются условиями автоматности отображения (оператора). Всякое отображение, удовлетворяющее этим условиям, будем называть автоматным отображением. Любое автоматное отображение может быть индуцировано некоторым автоматом.