Поняття кінцевого автомата

Процес побудови моделей

Ієрархічний підхід до отримання моделей

Рідко буває, що модель будується з урахуванням відразу всіх факторів, істотних для поведінки системи. Тому природний підхід, який реалізує принцип «від простого до складного», коли наступний крок робиться після досить докладного вивчення не дуже складної моделі. При цьому виникає ланцюжок (ієрархія) все більш повних моделей, кожна з яких узагальнює попередні, включаючи їх в якості випадку.

Етапи процесу побудови моделей можна уявити в такій послідовності:

1. Побудова моделі починається зі словесного опису об'єкта або явища, тобто сформіровивается предметна модель. Формулюється цілі дослідження моделі

2. Вибирається або формулюється закон, якому підпорядковується об'єкт. Модель записується в математичній формі.

3. Завершується побудова моделі. Проводиться селекція чинників, при якій відкидаються несуттєві і незначні фактори.

4. Побудована модель досліджується із застосуванням різних підходів і робиться висновок про її адекватності, тобто Відповідно об'єкту та цілям дослідження.

Теорія автоматів є розділом теоретичної кібернетики, в якій вивчаються математичні моделі - автомати. На основі цієї теорії система представляється у вигляді автомата, переробного дискретну інформацію і змінює свої внутрішні стану лише в допустимі моменти часу. Поняття «автомат» варіюється в залежності від характеру конкретно досліджуваних систем, від прийнятого рівня абстракції і доцільною мірою спільності.

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

Стан - це те, на що впливає управління, і що разом з управлінням визначає результат (вихід).

Різницеве ​​рівняння для стану такої системи має вигляд:

У рівнянні (1.4.1) віднімемо зліва і справа одну і ту ж величину x (t), тоді

Розділимо ліву частину рівняння (1.4.2) на Dt, Dt спрямуємо до нуля і в підсумку отримаємо запис диференціального рівняння в просторі станів:

Кінцевим автоматом називається автомат, у якого безліч внутрішніх станів, вхідних і вихідних сигналів є кінцевими множинами.

Таким чином, у порівнянні з універсальною моделлю існує обмеження: кінцівку множин. Дане обмеження не суттєво, що дозволяє широко застосовувати кінцеві автомати, в основному для синтезу пристроїв керування. Кінцеві безлічі (управлінь, станів, вихідних сигналів) називаються також алфавітами.

Кінцевий автомат є в загальному випадку динамічною системою, для якої характерні перехідні процеси, але сигнали неперервні, а дискретні. Поділ поточного часу пов'язують зі змінами внутрішнього стану і входу. Тому інтервали дискретності можуть бути неоднаковими. Внутрішні стани можуть мати різну ступінь деталізації. Тому можна говорити про більш швидкого і більш повільної тактності.

Як і у будь-який динамічної системи, робота кінцевого автомата описується двома функціями:

де x - змінна стану;

u - змінна управління;

y - змінна виходу;

t - момент часу (t = 0,1,2,3 ...).

Всі ці змінні в загальному випадку є векторами.

За допомогою цих двох функцій можна, знаючи початковий стан і послідовність управлінь, визначити стану і виходи в усі наступні моменти часу.

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

Таким чином, робота кінцевого автомата відбувається за такою схемою: в кожному t-му такті на вхід автомата, що знаходиться в стані x (t), подається деякий сигнал u (t). на який автомат реагує переходом в (t + 1) -м такті в новий стан x (t + 1) і видачею деякого вихідного сигналу.

За кількістю станів розрізняють кінцеві автомати з пам'яттю і без пам'яті. Автомати з пам'яттю мають більше одного стану, а автомати без пам'яті мають лише одним станом.

За характером звіту дискретного часу кінцеві автомати діляться на синхронні і асинхронні. У синхронних автоматах моменти часу, в які автомат зчитує вхідні сигнали, визначаються примусово сіхронізірующімі сигналами. Після чергового сигналу, з урахуванням ліченого, відбувається перехід в новий стан і видача сигналу на виході, після чого автомат може сприймати таке значення вхідного сигналу. Таким чином, реакція автомата на кожне значення вхідного сигналу закінчується за один такт, тривалість якого визначається інтервалом між сусідніми синхроімпульсами. Асинхронний автомат зчитує вхідний сигнал безперервно, і тому, реагуючи на досить довгий вхідний сигнал постійної величини, він може кілька разів змінювати стан, видаючи відповідне число вихідних сигналів, поки не перейде в стійкий стан, яке вже не може бути змінено даними вхідним сигналом.