1.7.3 Основна задача структурної теорії автоматів

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

Більш детально основна задача структурної теорії автоматів може бути сформульована в наведений нижче спосіб.

Нехай задана деяка скінченна множина автоматів у одному структурному алфавіті Х.

Назвемо дані автомати елементарними та припустимо, що кожний з елементарних автоматів є в розпорядженні в необмеженiй кількостi примiрників.

Нехай також задано довільний скінченний автомат А в тому самому структурному алфавіті Х.

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

1.8 Структурна повнота системи елементарних автоматів, особливості вирішення основної задачі структурної теорії автоматів, повнота системи переходів і виходів автоматів з пам’яттю, теорема про структурну повноту

1.8.1 Структурна повнота системи елементарних автоматів

Далеко не при будь-якому виборі системи елементарних автоматів основна задача структурної теорії автоматів має розв`язок.

Якщо основна задача структурної теорії має розв`язок (для довільного кінцевого автомату А), то систему елементарних автоматів називають структурно повною.

Тобто система елементарних автоматів називається структурно повною, якщо за допомогою автоматів даної системи можна побудувати структурний автомат, еквівалентний будь-якому наперед заданому абстрактному автомату A.

1.8.2 Ослаблена структурна повнота

Іноді користуються поняттям ослабленої структурної повноти.

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

1.8.3 Особливості вирішення основної задачі структурної теорії автоматів, логічні та запам’ятовуючі елементи

Далеко не для кожної структурно повної системи елементарних автоматів основна задача структурної теорії автоматів має ефективне рішення.

У загальному випадку, не існує алгоритмів, істотно більш простих, ніж метод перебору всіх варіантів, які розв`язують указану задачу.

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

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

У подальшому будемо розглядати один із можливих таких алгоритмів - канонічний метод структурного синтезу автоматів 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. Якою є основна думка теореми про структурну повноту ?