Дискретно-детерміновані моделі (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), на який автомат реагує переходом на (t+1)-ому такті новий стан z(t+1) і видачею деякого вихідного сигналу.

Залежно від способу визначення вихідного сигналу абстрактні кінцеві автомати (синхронні) поділяються на два типи:

1) F -автомат першого роду, також називаєтьсяавтомат Милі:

Рис.1 Граф автомата Милі

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

Для якого $ y (t) = \ psi [z (t)], t = 0,1,2. ; $

Рис.2 Граф автомата Мура

називаєтьсяавтомат Мура- функція виходів залежить від вхідний змінної x(t).

Щоб встановити кінцевий F - автомат, необхідно описати всі елементи безлічі $ F = $ .

Існує кілька способів завдання роботи F - автоматів серед яких найбільше застосування знайшли табличний, графічний та матричний.

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

Р-схеми прийнято називати імовірнісними автоматами, за допомогою яких можна визначити дискретні перетворення інформації з пам'яттю.

В іероятнісний автомат( англ, probabilistic automata) (ВА) - це дискретний потактний перетворювач інформації з пам'яттю, функціонування якого в кожному такті залежить тільки від стану пам'яті і може бути описано статистично.

Схеми імовірнісних автоматів(Р-схем)застосовуються:

  • у проектуванні дискретних систем, що виявляють статистичнозакономірна випадкова поведінка;
  • у визначенні алгоритмічних можливостей систем;
  • в обґрунтуванні меж доцільності їх використання;
  • у вирішенні задач синтезу за вибраним критерієм дискретних стохастичних систем, що задовольняють заданим обмеженням.

Математичне поняттяР-автоматаформується на поняттях, введених дляF'-автомата.

Нехай безлічG',елементами якого є всілякі пари деxi'і zs — елементи вхідної підмножиниX'і підмножини станів Z відповідно. Якщо є дві такі функції і,то з допомогою здійснюються відображення і , то кажуть, що (1) визначає кінцевий автомат детермінованого типу.

Введемо більш загальну математичну схему. Нехай Ф - безліч усіляких пар виду('zk', 'yj'),деyj'- елемент вихідного підмножиниY',тобто..Нехай у будь-який елемент множиниG'індукує на множині Ф певний закон розподілу наступного виду: