X1(n) Комб. Y(n)

x2(n) схема s1(n+1)

s1(n)

s2(n) s2(n+1)

П2

П1

Рис. 3.14 - Структурна схема кінцевого автомата

Комбінаційна схема автомата і її зв'язок з елементами пам'яті показана на рис. 3.15.

Таким чином, синтезований кінцевий автомат містить 4 елемента "не", три елементи "або", дев'ять елементів "і" і два елементи пам'яті.

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

Вихідне слово - послідовність вихідних сигналів, що видаються автоматом. Стани автомата - це комбінації станів елементів пристрою, що запам'ятовують.

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

x1(n) x2(n) s1(n) s2(n) s2(n)s1(n)x2(n)x1(n) KC

x1(n) 1 &

x2(n)



1 1 y(n)

& 1

&

1

&

s2

& 1 (n+1)

&

& s1

(n+1)

1

&

П2

s2(n)

П1 Пам'ять

s1(n)

Рис. 3.15 - Схема кінцевого автомата

3.11. Програмна реалізація логічних функцій і автоматів.

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

Під програмою будемо розуміти пронумеровану послідовність команд k_{1, …} , k_s, узятих із деякого фіксованого набору (системи команд). Програма працює над кінцевою множиною пронумерованих (або пойменованих ) двійкових елементів. Номер (або ім'я ) елемента називається його адресою ; ім'ям елементу часто буде служити ім'я логічної змінної, значення якої зберігаються в цьому елементі.

Система команд містить команди-оператори виду b:=f(a_{1, …} , a_p) (виконати операцію над вмістом елементів a_{1, …} , a_p і результат покласти в елемент b ) і двоадресні умовні переходи двох видів: 1) “якщо а, те i, інакше j ”( якщо a = 1, то перейти до виконання команди k_ί, інакше перейти до k_j ) ; 2 ) ” якщо ā ( a = 0 ) , то i , інакше j ”. Операція f ( a₁ , . . ., a_p ) - це логічна функція p перемінних ; зокрема, вона може бути константою 0 або 1. Якщо j - номер такої команди, то перехід можна вважати одноадресним : ” якщо a, то i, ( інакше перейти до наступної команди ) ”, а якщо i = j, то безумовним : ” перейти до i “. Довільна з команд зазначених типів може бути заключної, що вказується словом ” кінець “.

Процесом обчислення програми k₁, . . ., k_s називається послідовність кроків k ( 1 ), k ( 2 ), . . ., k ( t ), на кожному з який виконується одна команда програми. Ця послідовність визначається так : 1) k ( 1) = k1; 2) якщо k (1) = kr - оператор, то k ( i + 1 ) = k_r+1 ; 3) якщо k ( 1) - умовний перехід, то номер команди k ( i + 1 ) вказується цим переходом; 4) якщо k ( i ) - заключна команда, то процес обчислення зупиняється після її виконання. Число t називається часом її виконання.

Програма П обчисляє (або реалізує ) логічну функцію f ( х₁ , . . . , х_n ) = у, якщо для будь-якого двійкового набору σ = ( σ ₁ , . . . , σ _n ) при початковому стані пам'яті х₁ = σ ₁ , х₂ = σ ₂, . . ., х_n = σ _n (стан інших елементів несуттєвий ) програма через кінцеве число кроків зупиняється і при цьому в елементі у лежить величина f ( σ ₁ , . . . , σ _n).

Якщо під складністю схеми, що реалізує автомат, звичайно розуміється число елементів у схемі, то складність програми можна розуміти в різноманітних змістах: 1) число команд у тексті програми; 2) обсяг проміжної пам'яті, тобто число елементів для збереження проміжних результатів обчислень; 3) час обчислення, що буде характеризуватися двома величинами: середнім часом t_ср (П) =1/2ⁿ τ_р(σ) і максимальним часом t_макс(П) = max_ τ_р(σ), де сума і максимум беруться по всім 2ⁿ двійковим набором σ, а τ_р - час роботи програми П на наборі σ.

Будь-якій схемі, що реалізує функцію f і містить N елементів, неважко поставити у відповідність програму, що реалізує f і складається з N команд, у такий спосіб. Занумеруємо елементи схеми числами 1,2, . . ., n так, щоб на будь-якому шляху від входу до виходу номера елементів зростали; при цьому номер 1 одержить один із вхідних елементів, а номер N - вихідний елемент. Нехай елемент е_ί схеми реалізує функцію φ _ί і до його входів приєднані виходи елементів е_j1, . . ., е_jp ( деякі з них, можливо, є входами схеми). Поставимо елементу е_ί у відповідність або елемент а_ί і команду а_ί = φ_ί ( а_j1 , . . ., а_jp ), якщо ί ≠ N; або елемент у і команду << у : = φ N( а_j1, . . ., а_jp ) кінець >>, якщо ί = N. Одержимо програму, що не містить умовних переходів ( такі програми будемо називати операторними ), у якій порядок команд у точності відповідає нумерації елементів у схемі, а система команд - базису схеми.

Проблеми синтезу операторних програм в основному зводяться до проблем синтезу схем: зокрема питання функціональної повноти системи команд і мінімізації власного тексту операторної програми збігаються відповідно з задачами функціональної повноти системи функцій і про мінімізацію схем. Оскільки операторна програма не містить умовних переходів, час її обчислення на будь-якому наборі те саме. Звідси t_max = t_cp = N, тобто обидва види часової складності збігаються зі складністю тексту програми, і, отже, при достатньо великих n майже для усіх функцій близькі до 2ⁿ ⁄ n. Навпаки, проблема мінімізації пам'яті ( за рахунок багатократного використання одного елементу для декількох проміжних результатів ) для операторних програм є нетривиальною комбінаторною задачею.

Інший ”крайній “ вид програм, що обчислюють логічні функції, - програми, що складаються з команд виду в : = σ ( σ = 1 або σ = 0 ) і умовних переходів. Такі програми називаються бінарними програмами. Всяку булеву функцію F , що містить N букв, можна реалізувати бінарною програмою, що обчисляє F за час t_max = N і що містить N команд умовних переходів ( а також дві команди у = 1 і у = 0, що в оцінках не беруть участі ). Для опису методу реалізації використовуємо представлення програми у вигляді графа в який вершини відповідають командам, а ребра - переходам. Нехай G₁ - граф програми для функцій f₁ із початковою вершиною v₁₀ і двома заключними вершинами v_1z⁰ ( із командою у = 0 ) і v_1z¹ ( із командою у = 1 ) ; G₂ - граф програми для f₂ із початком v₂₀ і кінцями v_2z⁰ і v_2z¹. Тоді: 1) програма, граф G якої отриманий приєднанням G₂ до ”нуля“ G ₁ ( тобто ототожненням вершин v_1z⁰ і v₂₀¹ ; команда у : = 1 при цьому відкидаеться, обчислюють функцію f = f ₁ / f ₂; 2) програма, граф G якої отриманий приєднанням G ₂ до ”одиниці“ G ₁ ( ототожнюємо v_1z¹ і v₂₀ ), обчисляє f = f ₁  f₂; 3) програма, граф який отриман із G ₁ заміною команд у v_1z⁰ і v_1z¹ на інверсні, обчислює f ₁. Зауважимо, що в графі G - дві нульові заключні вершини. Їх необхідно ототожнювати.