![](/user_photo/2706_HbeT2.jpg)
Міністерство освіти, науки, молоді і спорту України
Національний університет «Львівська політехніка»
Звіт
До лабораторної роботи №3
З дисципліни «Моделювання систем»
На тему «Імітаційне моделювання процесу
Функціонування скінченого дискретного
стохастичного автомата»
Виконала
Студентка групи КН-31
Асіїв Андріана
Прийняв
Доцент Кузьмін О.В.
Львів-2012
Мета роботи - вивчити процес функціонування дискретного скінченого стохастичного автомата та знайти його ймовірності характеристики за даними експерименту.
І. ОСНОВНІ ПОЛОЖЕННЯ.
Математичні моделі автоматів вивчаються у розділі теоретичної кібернетики - теорії автоматів. Основним у цій теорії є представлення системи у вигляді автомата, який опрацьовує дискретну інформацію та змінює свої внутрішні стани в допустимі моменти часу. Автомат - це деякий пристрій, на вхід якого поступають вхідні сигнали, під дією яких залежно від внутрішнього стану на виході формуються вихідні сигнали, і відбувається перехід в інший внутрішній стан. Скінченим називається автомат, у якого множини внутрішніх станів, вхідних та вихідних сигналів скінченні. Скінченний автомат, характеризується скінченими множинами вхідних сигналів X (вхідний алфавіт), вихідних сигналів Y (вихідний алфавіт), станів Z (алфавіт станів), функціями виходів та переходів.
1.1. Дискретні детерміновані автомати.
Дискретні
детерміновані автомати (F-схеми)
описуються у вигляді шістки
,
де X,
Y,
Z
- множини відповідно вхідних, вихідних
сигналів та станів, Z0
- початковий стан,
,
- відповідно функції переходів та
виходів.
Автомат,
який описується F-схемою,
функціонує в дискретному автоматному
часі. У момент часу ti
автомат знаходиться в стані
,
сприймає на вході сигнал
,
генерує на виході сигнал
,
і після цього переходить у стан
,
.
Описана
послідовність дій відбувається миттєво.
Таким чином реалізується деяке відображення символів вхідного алфавіту в множину символів вихідного.
Автомат Мілі описується за допомогою таких функцій переходів та виходів:
(1)
Для автомата Мура функції виходів та переходів мають вигляд
(2)
За характером відліку дискретного часу автомати поділяються на синхронні та асинхронні. В синхронних автоматах моменти часу дії вхідних сигналів синхронізуються сигналом повної частоти (наприклад, ЕОМ). Асинхронний автомат може сприймати вхідні сигнали в довільні моменти часу (наприклад, автомат для продажу газет та журналів).
Функціонування F-автомата може бути описане одним з трьох способів: табличним, графічним та матричним.
Табличний спосіб вимагає побудови таблиць переходів та виходів (табл. 1, 2).
Таблиця 1
Таблиця переходів F-автомата
X |
Z
|
|||
|
|
... |
|
|
|
|
|
... |
|
Таблиця 2 .
Таблиця виходів F -автомата
X |
Z
|
|||
|
|
... |
|
|
|
|
|
... |
|
У
графовому представленні F-автомата,
вершини графу відповідають станам
автомата, а дуги, які їх з’єднують, тим
чи іншим переходам автомата із стану в
стан. Якщо вхідний сигнал, Хк
викликає перехід з стану Zi
в стан Zj,
то дуга, яка з’єднує Zj
з Zi,
позначається Хk.
Для задання функції виходів дуги графа
необхідно помітити вихідними сигналами.
Для автомата Мілі розмітка здійснюється
так: якщо вхідний сигнал Хk
діє на автомат, що знаходиться в стані
Zi,
то
дугу, яка виходить з Zi
і помічена Хk,
додатково помічають вихідним сигналом
.
Для
автомата Мура розмітка здійснюється
так: якщо вхідний сигнал Xk
діє на автомат, що знаходиться в стані
Zi,
викликає
перехід в стан Zj,
то
дугу, яка направлена в Zj
і помічена Xk,
додатково помічають вихідним сигналом
.
При
розв’язуванні задач моделювання
найбільш зручною є матрична форма
представлення автомата.
Матриця станів автомата С
являє собою квадратну матрицю
,
рядки якої відповідають вихідним
станам, а стовпці - станам переходу.
Елемент
,
який знаходиться на перетині і-го
рядку та j-го
стовпця, у випадку автомата Мілі
відповідає вхідному сигналу Xk,
що викликає перехід із стану Zi
в стан Zj,
та вихідному сигналу ys,
який при цьому генерується.
Для
F-автомата
Мура Cij
дорівнює множині вхідних сигналів на
переході
,
а вихід описується вектором виходів
,
і-a
компонента
якого - вихідний сигнал, що відповідає
стану Zi.
1.2. Диcкретно-стохаcтичні автомати.
У загальному випадку ймовірнісний автомат являє собою дискретний потактний перетворювач інформації з пам’яттю, функціонування якого в кожному такті залежить лише від стану пам’яті і може бути описаний статистично.
Застосування схем ймовірнісних автоматів (Р-схем) має важливе значення для розвитку методів проектування дискретних систем, які виявляють статистично закономірну поведінку, обґрунтування алгоритмічних можливостей таких систем та доцільності їх використання, а також для розв’язування задач синтезу дискретних стохастичних систем за обраним критерієм з урахуванням обмежень.
Математично
Р-автомат
описується з використанням основних
понять F-автомату.
Розглянемо множину G,
елементами якої є різноманітні пари
,
де xi
та zs
- елементи підмножини відповідно вхідних
сигналів X
та станів Z.
Якщо існують дві такі функції φ
та ψ,
за допомогою яких здійснюється
відображення
GZ
та
GY,
то п'ятірка P=<Z,
X,
Y,
φ, ψ>
відображає детермінований автомат.
Розглянемо
більш загальну математичну схему. Нехай
Ф
- множина різноманітних пар виду
,
де yj
-
елемент Y.
Поставимо вимогу, щоб довільний
елемент множини G
спричиняв на множині Ф
деякий закон розподілу:
Елементи
з Ф
(xi,zs) b11 b12 ... bk,j-1 bkj
При
цьому
,
bkj
- ймовірності переходу автомата в стан
Zk
та генерація вихідного сигналу yj,
якщо він знаходився в стані Zs
та на його вхід в цей момент прийшов
сигнал xi.
Число
таких розподілів, які подаються у вигляді
таблиць, дорівнює числу елементів
множини G.
Позначимо множину таких таблиць В
і отримаємо
опис
стохастичного дискретного автомата в
вигляді четвірки
.
Нехай елементи множини G спричиняють на множинах Y та Z деякі закони розподілу:
Елементи
з Y
(xi,zs)
Елементи
з Z
(xi,zs)
При
цьому
,
,
де pk
та qj
-
ймовірності переходу автомата в стан
Zk
та генерації вихідного сигналу yj
відповідно за
умови,
що Р-автомат
знаходився в стані Zs
та на його вхід прийшов сигнал xi.
Якщо для всіх k
та j
справедливе співвідношення
,
то такий автомат будемо називати
стохастичним автоматом Мілі. Ця вимога
є умовою незалежності розподілів для
нового стану Р-автомата
та його вихідного сигналу.
Нехай визначення вихідного сигналу Р-автомата залежить лише від того стану, в якому знаходится автомат в поточному такті. Іншими словами, нехай кожен елемент вихідної множини Y спричиняє розподіл ймовірностей виходів виду:
Елементи
з Y
де
,
Si
-
ймовірність генерації вихідного сигналу
уi,
за умови, що Р-автомат
знаходився в стані Zk.
Якщо
для всіх k
та i
справедливе співвідношення
,
то такий автомат називається стохастичним
автоматом Мура.
Таким чином, поняття Р-автоматів Мілі та Мура введені аналогічно до відповідних детермінованих автоматів.
Окремий випадок Р-автомата - це автомат, у якого перехід в новий стан або вихідний сигнал визначаються детерміновано. В першому випадку такий автомат називається Z-детермінованим стохастичним автоматом, в другому - Y-детермінованим.