Цифрові автомати з пам'яттю

Математичною моделлю дискретного пристрою з кінцевою пам'яттю є абстрактний автомат А. Автомат А задається множинами X, Y, Z, а також двома функціями d і l. Автомат

де - множина вхідних сигналів (вхідний алфавіт);

- множина вихідних сигналів (вихідний алфавіт);

- множина станів (алфавіт станів); d - функція переходів автомата; l - функція виходів автомата; z₀ є Z - початковий стан автомата.

Абстрактний автомат (мал.4.1) має один вхідний і один вихідний канали. У кожен момент t=0,l,2,... дискретні моменти автомат знаходиться у визначеному стані Z(t) з безлічі Z станів автомата, причому в початковий момент t=0 він завжди знаходиться в початковому стані z (о) = Z_o. У момент t, будучи в стані z(t), автомат здатний сприйняти на вхідному каналі сигнал x(t) X і видати на вихідному каналі сигнал Y(t)=l(z(t),(t)), переходячи в стан z(t+1)=d(z(t),x(t)), z(t)ÎZ. y(t)ÎY.

Рис. 4.1. Абстрактний автомат

Зміст поняття абстрактного автомата полягає в тому, що він реалізує деяке відображення безлічі слів вхідного алфавіту X у безліч слів вихідного алфавіту Y, тобто, якщо на вхід автомата, встановленого в початковий стан z₀, подавати буква за буквою деяку послідовність букв вхідного алфавіту Х(0), Х(1), Х(2),..., що є вхідним словом, то на виході автомата будуть послідовно з'являтися букви вихідного алфавіту Y(0), Y(l), Y(2),..., (вихідне слово). Звідси до кожного вхідного слова видається відповідне йому вихідне слово. Таким чином, одержуємо відображення Y, індуковане абстрактним автоматом.

Розрізняють детерміновані і ймовірнісні автомати. У детермінованих автоматах функції переходів і виходів однозначні: кожній парі z(t) і x(t) відповідає єдина пара z(t+l) і y(t). Це значить, що вихідний сигнал автомата в момент часу t і стан, у яке він переходить у момент t+l, однозначно визначаються станом і значенням вхідного сигналу в момент часу t. Більшість реальних схем працюють як детерміновані автомати. Надалі будемо розглядати тільки детерміновані автомати.

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

Дата добавления: 2015-06-27