Основи теорії цифрових автоматiв з пам`яттю: Методичні рекомендації та контрольні завдання до виконання лабораторної роботи з дисципліни "Комп’ютерна логіка", страница 10

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

У подальшому будемо розглядати один із можливих таких алгоритмів - канонічний метод структурного синтезу автоматів iз пам’яттю (КМ), який оперує з елементами-автоматами (зі специфічними властивостями) двох класів:

1) логічними елементами - автоматами без пам’яті, або, як їх ще називають, автоматами з одним внутрішнім станом;

2) запам’ятовуючими елементами - автоматами з пам’яттю, або, як ще кажуть, автоматами, що мають більше одного внутрішнього стану.

1.8.4 Повнота системи переходів і виходів автоматів iз пам’яттю

Автомат iз пам’яттю володіє повною системою переходів, якщо рівняння в = δ(a,x) (де а,в є Z – деякі стани, x – вхідний сигнал, δ – функція переходів) має рішення відносно х для будь-якої пари станів (а,в).

Автомат iз пам’яттю володіє повною системою виходів, якщо для будь-якого у має рішення відносно х рівняння .

1.8.5 Теорема В.М. Глушкова про структурну повноту

Система елементарних автоматів, яка включає в себе деяку функціонально повну систему логічних елементів та автомат Мура з нетривіальною пам’яттю (з кількістю внутрішніх станів, бiльшою за одиницю), що володіє повною системою переходів та виходів, є структурно повною.

Більше того, існує алгоритм – канонічний метод структурного синтезу автоматів з пам’яттю, який дає розв`язок основної задачі структурної теорії автоматів і дозволяє звести задачу структурного синтезу довільних кінцевих автоматів iз пам’яттю до задачі структурного синтезу комбінаційних схем.

2 КОНТРОЛЬНІ ПИТАННЯ

1. Сформулювати iнформаційні основи цифрових автоматів.

2. Охарактеризувати особливостi абстрактної теорії автоматів.

3. Назвати способи задавання абстрактних автоматiв Мілі та Мура.

4. Розкрити поняття часткового абстрактного автомату.

5. Якi iснують способи задавання автоматних вiдображень ?

6. Сформулювати поняття події.

7. Що являє собою канонiчна множина подiй ?

8. Яку роль вiдiграєалгебра подiй ?

9. Охарактеризувати тотожності алгебри подій.

10. Виконати огляд видатних подій.

11. Сформулювати поняття регулярного виразу.

12. Що таке циклiчна глибина регулярних виразiв i подiй ?

13. Чим вирiзняються нескінченнi нерегулярнi події ?

14. Сформулювати теорему Кліні про зв’язок скінченних автоматів і регулярних подій.

15. Яку роль відіграє наслiдок теореми Клiнi ?

16. Охарактеризувати в цiлому структурну теорію автоматів.

17. За яких умов має мiсце cтруктурна повнота системи елементарних автоматів ?

18. Назвати особливості розв`язування основної задачі структурної теорії автоматів.

19. Сформулювати поняття повноти системи переходів і виходів автоматів iз пам’яттю.

20. Якою є основна думка теореми про структурну повноту ?

3 ІНДИВІДУАЛЬНІ КОНТРОЛЬНI ЗАВДАННЯ

ЗАВДАННЯ 1.Перевизначити автомат Мура, що був заданий позначеною таблицею переходів i вiдповiдним їй графом (див. таблицю 1 i рисунок 3 основних теоретичних вiдомостей до лабораторноїроботи):

а) модифiкувати позначену таблицю переходiв;

б) додати ще один стан автомату.

ЗАВДАННЯ 2.Виконати iнтерпретацію абстрактного автомату Мура, отриманого у пiдсумку виконання завдання 1, як абстрактного автомату Мілі, аналогiчно тому, як виконувалася процедура iнтерпретації в основних теоретичних вiдомостях до лабораторної роботи (див. таблицi 2, 3 i рисунок 4 вище за текстом).

Додаток А

Вимоги до оформлення, захисту та оцінювання

лабораторних робіт

Під час захисту лабораторної роботи, студент повинен здійснити:

− коротке викладення теоретичних основ і змісту визначальних етапів     виконання роботи;

− демонстрацію результатів роботи;

− відповіді на питання викладача;

− подання підсумкового звіту про виконання роботи.

Звіт з лабораторної роботи повинен містити такі складові частини:

− титульний аркуш (зразок оформлення знаходиться далі, в Додатку Б);

− формулювання теми та мети лабораторної роботи;