8.2.3.2. Мови опису функціонування автоматів

Длятого, щоб задати абстрактний автомат, потрібно задати всі п'ять об'єктів

Множини X,S,Y задаються як звичайні множини в математиці, наприклад, простим перелічуванням всіх її елементів, тому їх задання на практиці не викликає ніяких труд­нощів.

Найбільш трудомістким є задання функцій, які власне і визначають алгоритм

функціонування автомату. Для опису алгоритму функціонування автомату, тобто для задання, існують різні засоби, які часто називають мовами. Існують стандартні та

початкові мови. Стандартні мови задають автомат одним із трьох способів: матрично (таблично), графічно, аналітично. До початкових мов відносять первісні таблиці вклю­чень, логічні схеми алгоритмів і граф-схеми алгоритмів. Стандартні мови частіше засто­совуються для задання автоматів загального виду, в той же час початкові мови знайшли широке застосування для часткових автоматів.

Мова матриць (таблиць) передбачає наявність двох таблиць: таблиці переходів і та­блиці виходів, або однієї таблиці з'єднань.

Таблиця переходів задає відображення X х S -->S, тобто задає функцію переходів

Приклад. Нехай на автомат поступають вхідні сигнали, які мають три букви, та нехай він має чотири стани: X= {х_р х₂, x₃,}, S = {s₁ s₂, s₃ s₄.} В табл. 8.1 описано повністю визна­чений автомат для даного прикладу.

Таблиця 8.1

З першого рядка табл. 8.1 видно, що перебуваючи в стані S1при поступленні вхідно­го сигналу X1автомат не змінює свого стану, так само як і при поступленні вхідного сиг­налу ХЗ, а при поступленні вхідного сигналу Х2 він перейде в стан S2.Подібним чином можна провести аналіз інших рядків таблиці.

Якщо автомат частковий, то для пар (х_i s_j,),для яких стан не визначений, в клітинці таблиці ставиться прочерк. Як видно, вигляд таблиці переходів не залежить від того, який тип автомату використовується: Мілі, Мура чи С-автомат.

Таблиці виходів цих автоматів відрізняються.

У клітинці таблиці виходів автомату Мілі ставиться вихідний сигнал у , який фор­мує автомат Мілі, що знаходиться в стані S_jі на вході якого діє сигнал х_i. Приклад по­вністю визначеного автомату Мілі з вхідним алфавітом X = {х₁ х₂, х₃}, алфавітом станів; S = {s₁ s₂ s₃ s₄ } та вихідним алфавітом У = {у₁ у₂, у₃ } наведено в табл. 8.2.

289

Таблиця 8.2

З першого рядка табл. 8.2 видно, що перебуваючи в стані S1 при поступленні вхідного сигналу XI на виході автомату буде сформовано сигнал Y1, так само, як і при поступлен­ні вхідного сигналу Х2, а при поступленні вхідного сигналу ХЗ на виході автомату буде сформовано сигнал Y2. Подібним чином можна провести аналіз інших рядків таблиці.

В таблиці виходів повністю визначеного автомату Мура кожному стану автомату призначається відповідний вихідний сигнал у . Приклад повністю визначеного автомату Мура з алфавітом станів S = {s_p s₂, s₃, s₄ } та вихідним алфавітом Y = (у₁, у₂, у₃} наведено в табл. 8.3.

Таблиця 8.3

З табл. 8.3 видно, що стану S1 та S2 автомату відповідає вихідний сигнал Y1, стану S3 відповідає вихідний сигнал Y2, а стану S4 відповідає вихідний сигнал Y3.

С-автомат буде задаватися двома таблицями виходів, перша з яких відповідає табли­ці виходів автомату Мілі, а друга - таблиці автомату Мура.

На практиці таблиці переходів і таблиці виходів часто суміщаються в одну суміщену таблицю. Табл. 8.4 є суміщеною таблицею автомату Мілі для вищенаведеного прикладу.

Таблиця 8.4

З першого рядка табл. 8.4 видно, що перебуваючи в стані S1 при поступленні вхідно­го сигналу X1 автомат залишиться в тому ж стані, а на виході автомату буде сформовано сигнал Y1, при поступленні вхідного сигналу Х2 автомат перейде в стан S2, а на виході автомату буде сформовано сигнал Y1, при поступленні вхідного сигналу ХЗ автомат за­лишиться в тому ж стані, а на виході автомату буде сформовано сигнал Y2. Подібним чином можна провести аналіз інших рядків таблиці.

290

Як вже зазначилось вище, можна задати керуючий автомат за допомогою єдиної та­блиці з'єднань. Таблиця з'єднань абстрактного автомату є квадратною і містить стільки стовпців та рядків, скільки різних станів має даний автомат. В клітинці ставиться вхід­ний сигнал, під дією якого відбувається перехід автомату зі стану в стан. Якщо матри­цею з'єднань задається автомат Мілі, то разом з вхідним сигналом вказується вихідний сигнал, який автомат Мілі видає, виконуючи перехід (табл. 8.5).

Таблиця 8.5

З першого рядка табл. 8.5 видно, що автомат залишається в тому ж стані S1при посту­пленні вхідних сигналів XIта ХЗ, і при цьому на його виході будуть відповідно сигнали Y1,та Y2,та переходить в стан S2при поступленні вхідного сигналу Х2, і при цьому на його виході буде сигнал Y1.Подібним чином можна провести аналіз інших рядків таблиці.

Для автомату Мура в матриці з'єднань вихідні сигнали ставляться біля станів авто­мату, які ідентифікують рядки матриці.

Мова графіки передбачає застосування для задання абстрактного автомату орієнтова­ного графа. Стан автомату зображається вершинами графа, а переходи між станами - ду­гами між відповідними вершинами. При цьому конкретній дузі графа приписується буква х. вхідного алфавіту автомату, яка вказує на перехід при поступленні цього сигналу.

Якщо граф зображає автомат Мілі (рис. 8.7), то вихідні сигнали автомату ставляться на дугах графа (згідно з таблицею виходів) разом з буквою вхідного сигналу. Тут в якості прикладу взято автомат Мілі, описаний в табл. 8.4.

Рис .8.7. Граф автомату Мілі

Якщо графом зображається автомат Мура (рис. 8.8), то вихідні сигнали автомату ставляться біля вершини графа відповідно до таблиці виходів автомату (табл. 8.3).

291

Рис. 8.8. Граф автомату Мура

Мова аналітичних виразів передбачає задання автомату шляхом запису для кожного стану автомату відображення F_sj., яке містить набори з трьох об'єктів s_n,x_i y_k, причому тільки таких, які вказують на наявність переходу автомату зі стану s . в стан s_n при дії вхідного сигналу х_i і видачі при цьому вихідного сигналу у_к.

Приклад: