Міністерство освіти, науки, молоді і спорту України

Національний університет «Львівська політехніка»

Звіт

До лабораторної роботи №3

З дисципліни «Моделювання систем»

На тему «Імітаційне моделювання процесу

Функціонування скінченого дискретного

стохастичного автомата»

Виконала

Студентка групи КН-31

Асіїв Андріана

Прийняв

Доцент Кузьмін О.В.

Львів-2012

Мета роботи - вивчити процес функціонування дискретного скінченого стохастичного автомата та знайти його ймовірності характеристики за даними експерименту.

І. ОСНОВНІ ПОЛОЖЕННЯ.

Математичні моделі автоматів вивчаються у розділі теоретичної кібернетики - теорії автоматів. Основним у цій теорії є представлення системи у вигляді автомата, який опрацьовує дискретну інформацію та змінює свої внутрішні стани в допустимі моменти часу. Автомат - це деякий пристрій, на вхід якого поступають вхідні сигнали, під дією яких залежно від внутрішнього стану на виході формуються вихідні сигнали, і відбувається перехід в інший внутрішній стан. Скінченим називається автомат, у якого множини внутрішніх ста­нів, вхідних та вихідних сигналів скінченні. Скінченний автомат, харак­теризується скінченими множинами вхідних сигналів X (вхідний алфа­віт), вихідних сигналів Y (вихідний алфавіт), станів Z (алфавіт станів), функціями виходів та переходів.

1.1. Дискретні детерміновані автомати.

Дискретні детерміновані автомати (F-схеми) описуються у вигляді шістки , де X, Y, Z - множини відпо­відно вхідних, вихідних сигналів та станів, Z₀ - початковий стан, , - відповідно функції переходів та виходів.

Автомат, який описується F-схемою, функціонує в дискретному авто­матному часі. У момент часу t_i автомат знаходиться в стані , сприймає на вході сигнал , генерує на виході сигнал , і після цього переходить у стан , . Описана послідовність дій відбувається миттєво.

Таким чином реалізується деяке відображення символів вхідного алфа­віту в множину символів вихідного.

Автомат Мілі описується за допомогою таких функцій переходів та виходів:

(1)

Для автомата Мура функції виходів та переходів мають вигляд

(2)

За характером відліку дискретного часу автомати поділяються на синхронні та асинхронні. В синхронних автоматах моменти часу дії вхідних сигналів синхронізуються сигналом повної частоти (наприклад, ЕОМ). Асинхронний автомат може сприймати вхідні сигнали в довільні моменти часу (наприклад, автомат для продажу газет та журналів).

Функціонування F-автомата може бути описане одним з трьох способів: табличним, графічним та матричним.

Табличний спосіб вимагає побудови таблиць переходів та виходів (табл. 1, 2).

Таблиця 1

Таблиця переходів F-автомата

X	Z
			...
			...

Таблиця 2 .

Таблиця виходів F -автомата

X	Z
			...
			...

У графовому представленні F-автомата, вершини графу відповідають станам автомата, а дуги, які їх з’єднують, тим чи іншим переходам автомата із стану в стан. Якщо вхідний сигнал, Х_к викликає перехід з стану Z_i в стан Z_j, то дуга, яка з’єднує Z_j з Z_i, позначається Х_k. Для задання функції виходів дуги графа необхідно помітити вихідними сигналами. Для автомата Мілі розмітка здійснюється так: якщо вхідний сигнал Х_k діє на автомат, що знаходиться в стані Z_i, то дугу, яка виходить з Z_i і помічена Х_k, додатково помічають вихідним сигналом . Для автомата Мура розмітка здійснюється так: якщо вхідний сигнал X_k діє на автомат, що знаходиться в стані Z_i, викликає перехід в стан Z_j, то дугу, яка направлена в Z_j і помічена X_k, додатково помічають вихідним сигналом .

При розв’язуванні задач моделювання найбільш зручною є матрична форма представлення автомата. Матриця станів автомата С являє собою квадратну матрицю , рядки якої відповідають вихідним ста­нам, а стовпці - станам переходу. Елемент , який знахо­диться на перетині і-го рядку та j-го стовпця, у випадку автомата Мілі відповідає вхідному сигналу X_k, що викликає перехід із стану Z_i в стан Z_j, та вихідному сигналу y_s, який при цьому генерується.

Для F-автомата Мура C_ij дорівнює множині вхідних сигналів на переході , а вихід описується вектором виходів , і-a компонента якого - вихідний сигнал, що відповідає стану Z_i.

1.2. Диcкретно-стохаcтичні автомати.

У загальному випадку ймовірнісний автомат являє собою дискретний потактний перетворювач інформації з пам’яттю, функціонуван­ня якого в кожному такті залежить лише від стану пам’яті і може бути описаний статистично.

Застосування схем ймовірнісних автоматів (Р-схем) має важливе значення для розвитку методів проектування дискретних систем, які виявляють статистично закономірну поведінку, обґрунтування алгоритмічних можливостей таких систем та доцільності їх використання, а також для розв’язування задач синтезу дискретних стохастичних систем за обраним критерієм з урахуванням обмежень.

Математично Р-автомат описується з використанням основних понять F-автомату. Розглянемо множину G, елементами якої є різноманіт­ні пари , де x_i та z_s - елементи підмножини відповідно вхідних сигналів X та станів Z. Якщо існують дві такі функції φ та ψ, за допомогою яких здійснюється відображення GZ та GY, то п'я­тірка P=<Z, X, Y, φ, ψ> відображає детермінований автомат.

Розглянемо більш загальну математичну схему. Нехай Ф - множина різноманітних пар виду , де y_j - елемент Y. Поставимо вимо­гу, щоб довільний елемент множини G спричиняв на множині Ф деякий закон розподілу:

Елементи з Ф

(x_i,z_s) b₁₁ b_{12 ...} b_k,j-1 b_kj

При цьому , b_kj - ймовірності переходу автомата в стан Z_k та генерація вихідного сигналу y_j, якщо він знаходився в стані Z_s та на його вхід в цей момент прийшов сигнал x_i.

Число таких розподілів, які подаються у вигляді таблиць, дорівнює числу елементів множини G. Позначимо множину таких таблиць В і отримаємо опис стохастичного дискретного автомата в вигляді четвірки .

Нехай елементи множини G спричиняють на множинах Y та Z деякі закони розподілу:

Елементи з Y

(x_i,z_s)

Елементи з Z

(x_i,z_s)

При цьому , , де p_k та q_j - ймовірності переходу автомата в стан Z_k та генерації вихідного сигналу y_j відповідно за умови, що Р-автомат знаходився в стані Z_s та на його вхід прийшов сигнал x_i. Якщо для всіх k та j справедливе співвідношення , то такий автомат будемо називати стохастичним автоматом Мілі. Ця вимога є умовою незалежності розподілів для нового стану Р-автомата та його вихідного сигналу.

Нехай визначення вихідного сигналу Р-автомата залежить лише від того стану, в якому знаходится автомат в поточному такті. Іншими словами, нехай кожен елемент вихідної множини Y спричиняє розподіл ймо­вірностей виходів виду:

Елементи з Y

де , S_i - ймовірність генерації вихідного сигналу у_i, за умови, що Р-автомат знаходився в стані Z_k.

Якщо для всіх k та i справедливе співвідношення , то такий автомат називається стохастичним автоматом Мура.

Таким чином, поняття Р-автоматів Мілі та Мура введені аналогічно до відповідних детермінованих автоматів.

Окремий випадок Р-автомата - це автомат, у якого перехід в новий стан або вихідний сигнал визначаються детермі­новано. В першому випадку такий автомат називається Z-детермінованим стохастичним автоматом, в другому - Y-детермінованим.