Основні поняття теорії цифрових автоматів

 

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

Цифровим автоматом (ЦА) називають пристрій, призначений для обробки та перетворення цифрової інформації. Найбільш розповсюдженим типом цифрових автоматів є комп’ютери.

Цифровим автоматом вважаються пристрої, які характеризуються набором деяких внутрішніх станів , в які потрапляє автомат під впливом вхідних сигналів і відповідних команд розв’язання задачі (Рис. 2).

 

ЦА             А={аі(t)}

           Х(t)                                              Y(t)

Рис. 2 – Цифровий автомат

 

Відповідно до Рис. 2, математичною моделлю ЦА є деякий абстрактний автомат, який задається таким чином, в початковий момент часу t = t₀, внутрішній стан автомата а(t₀) = a₁ і зберігається таким до моменту часу t = t₁, коли змінюється на стан а₂, ця зміна відбувається під впливом вхідного сигналу Х(t₁). При цьому формується вихідний сигнал Y(t₁)=Y₁, який визначається як функція від внутрішнього стану a₁ і вхідного сигналу х₁: Y=λ(a₁, х₁). В загальному випадку вважається, що при поданні довільного сигналу х_і автомат переходить від стану а(t) в стан а(t+1), який, в свою чергу, є функцією від попереднього стану і вихідного сигналу. В результаті цього переходу виробляється відповідний сигнал Y.

Абстрактний ЦА описується шістьма основними параметрами:

- а₁ – початковий стан автомата;

- А = { } - множина (алфавіт) внутрішніх станів;

- Х = { } - алфавіт вхідних сигналів;

- Y = { } – алфавіт вихідних сигналів;

- δ = { } – сукупність функцій переходу автомата з одного стану в інший;

- λ = { } – сукупність функцій виходу автомата.

Сукупність правил переходу автомата з одного стану в інший залежно від вхідної інформації і внутрішніх станів називається алгоритмом перетворення інформації в цифровому автоматі.

На відміну від абстрактного автомата, реально використовуються кінцеві автомати, які мають кінцеві множини вхідних сигналів, вихідних сигналів та внутрішніх станів. Всі кінцеві автомати поділяються на цілком визначені, у яких область визначення D функцій δ та λ збігається з множиною перетину алфавітів вхідного та станів, яка є в свою чергу множиною пар ; та нецілком визначені часткові кінцеві автомати, для яких функції внутрішніх станів і вихідних сигналів δ та λ визначаються не для всіх пар , Крім того кінцеві автомати підрозділяють за виглядом функцій виходів  та переходів . За цією ознакою автомати поділяються на автомати Мілі та Мура.

Будь-який автомат можна описати функцією стану і вихідною функцією:

                               (3)

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

                               (4)