Дискретно-детерминистични модели (F-схеми)

Дискретно-детерминистични модели (F-схеми)Редактиране

Основният тип дискретно-детерминирани модели е краен автомат.

Краен автомате дискретен преобразувател на информация, способен да превключва от едно състояние в друго под въздействието на входни сигнали и да генерира сигнали на изхода. Това е автоматс памет. За да се организира паметта, времето на автомата и понятиетосъстояние на автоматасе въвеждат в описанието на автомата.

Концепцията"състояние"на автомата означава, че изходният сигнал на автомата зависи не само от входните сигнали в даден момент от време, но също така взема предвид входните сигнали, идващи по-рано. Това позволява времето да бъде елиминирано като изрична променлива и изходите да бъдат изразени като функция на състояния и входове.

Всеки преход на автомата от едно състояние в друго е възможен не по-рано от дискретен интервал от време. Освен това, самият преход се счита за мигновен, т.е. преходните процеси в реалните вериги не се вземат предвид.

Има два начина за въвеждане на автоматното време, според които автоматите се делят насинхроннииасинхронни.

Присинхроннитеавтомати моментите от време, в които се записват промените в състоянието на автомата, се задават от специално устройство - генератор на тактови сигнали. Освен това сигналите пристигат на равни интервали от време - $ \Delta t $ . Честотата на тактовия генератор е избрана така, че всеки елемент на автомата да има време да завърши работата си, преди да се появи следващият импулс.

Васинхроннияавтомат моментите на преминаване на автомата от едно състояние в друго не са предварително определени и зависят от конкретни събития. Такиваавтомати, дискретният интервал е променлив.

Има същодетерминистичниивероятностни автомати.

Вдетерминистичнитеавтомати, поведението и структурата на автомата във всеки момент от време се определят еднозначно от текущата входна информация и състоянието на автомата.

Ввероятностнитеавтомати те зависят от произволен избор.

Абстрактно един краен автомат може да бъде представен като математическа верига (F - верига), която се характеризира с шест вида променливи и функции:

  1. крайно множество x(t) от входни сигнали (входна азбука);
  2. крайно множество y(t) от изходни сигнали (изходна азбука);
  3. крайно множество z(t) от вътрешни състояния (азбука на състоянията);
  4. начално състояние на автомата z0 , ;
  5. функцията на преходите $ \varphi(z,x) $ на автомата от едно състояние в друго;
  6. изходна функция $ \psi(z,x) $ на автомата.

Абстрактният краен автомат има един вход и един изход. Във всяко дискретно време t=0,1,2. F-автоматът се намира в определено състояние z(t) от множеството Z-състояния на автомата, като в началния момент t=0 винаги е в началното състояние z(0)=z0 . В момента t, намирайки се в състояние z(t), автоматът е в състояние да възприеме сигнала $ x(t)\in X $ на входния канал и да изведе сигнала $ y(t)=\psi [z(t),x(t)] $ на изходния канал, преминавайки към състоянието $ z(t+1)=\varphi[z(t),x(t)] $ , където $ z(t)\in Z,x(t)\in X $ .

Абстрактен краен автомат прилага някакво преобразуване на набора от думи на входната азбука X към набора от думи на изходната азбука Y, т.е. ако на входа на крайния автомат, зададен в началното състояние z0, са дадени в някаква последователност буквите от входната азбука $ x(0),x(1),x(2). $,които съставят входната дума, тогава буквите от изходната азбука $ y(0),y(1),y(2) последователно ще се появят на изхода на автомата. $ формиране на изходната дума.

Следователно работата на крайния автомат протича по следната схема: при всеки t-ти цикъл на входа на автомата в състояние z(t) се подава някакъв сигнал x(t), на който автоматът реагира, като преминава към новото състояние z(t+1) в (t + 1)-тия цикъл и издава някакъв изходен сигнал.

В зависимост от това как е дефиниран изходният сигнал, абстрактнитеавтомати (синхронни) се разделят на два вида:

1) F -автомат от първи вид, наричан ощеавтомат на Мили:

Фиг.1 Автоматна графика на Мили

2) F -автомат от втори вид:

За което: $ y(t)=\psi[z(t)],t=0,1,2. ; $

Фиг. 2 Графика на автомата на Мур

се наричаавтомат на Мур- изходната функция не зависи от входната променлива x(t).

За да се зададе краен F-автомат, е необходимо да се опишат всички елементи от множеството $ F= $ .

Има няколко начина за настройка на работата на F - автоматите, сред които най-широко използваните са табличен, графичен и матричен.

Дискретни стохастични модели (P-схеми) Редактиране

R-схемите обикновено се наричат ​​вероятностни автомати, с помощта на които е възможно да се определят дискретни трансформации на информация с памет.

Вероятностни автомати(на английски, probabilistic automata) (BA) е дискретен преобразувател на информация стъпка по стъпка с памет, чиято работа във всяка стъпка зависи само от състоянието на паметта и може да бъде описана статистически.

Използват се схеми на вероятностни автомати(P-схеми):

  • при проектирането на дискретни системи, които показват статистическиредовно произволно поведение;
  • при определяне на алгоритмичните възможности на системите;
  • при обосноваване на границите на целесъобразността на тяхното използване;
  • при решаване на задачи за синтез според избрания критерий на дискретни стохастични системи, които удовлетворяват зададени ограничения.

Математическата концепцияP-автоматсе формира върху понятията, въведени заF'-автомат.

Нека множествотоG',, чиито елементи са всички възможни двойки, къдетоxi'и zs са съответно елементите на входното подмножествоX'и подмножеството от състояния Z. Ако има две такива функции и,, тогава те се използват за реализиране на преобразувания и , тогава казваме, че (1) дефинира краен автомат от детерминистичен тип.

Нека въведем една по-обща математическа схема. Нека Ф е набор от всички възможни двойки от формата('zk', 'yj'),къдетоyj'е елемент от изходното подмножествоY',.Нека всеки елемент от множествотоG'индуцира върху множеството Ф някакъв закон на разпределение от следния вид: