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

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

1.7.2 Закони функціонування автоматів Мілі і автоматів Мура у структурній теорії автоматів

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

В абстрактній теорії автоматів було зручніше (щоб уникнути створення різних теорій для автоматів першого та другого роду) відносити вхідні та вихідні сигнали до моменту переходу автомату з одного стану в інший.

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

При вказаному способі відліку часу, визначення закону функціонування автоматів першого роду (автоматів Мiлі) буде мати вигляд

а(1+1)=d(а(t), x(t)),

y(t)=l(a(t), x(t)), t=0,1,2,...

Закон функціонування автоматів Мура набуде вигляду

а(t+1)=d(а(t),x(t)),

y(t)=l(a(t)), t=0,1,2,...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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