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

Якщо застосувати дану процедуру до автомату Мура, поданого графом на рисунку 3, то отримаємо еквівалентний автомат Мілі, заданий наведеними нижче: таблицями переходiв (лiворуч) i виходiв (праворуч); графом.

Таблиця 2                                                     Таблиця 3

	1	2	3	4
X	2	3	3	2
Y	1	4	4	1

	1	2	3	4
X	u	Υ	Υ	U
Y	u	Υ	Υ	U

Рисунок 4

1.4 Частковi абстрактнi автомати

1.4.1 Поняття часткового абстрактного автомату

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

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

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

У тих місцях таблиць ТП i ТВ, в яких відповідні їм функції не визначені, як правило, ставлять риску.

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

Частковi автомати також розділяють на абстрактнi автомати першого та другого роду, автомати Мілі та Мура.

1.4.2 Заборонені та допустимі слова для даного часткового автомату

Для визначення поняття еквівалентності часткового автомату, необхідно встановити, що слід розуміти під відображенням, що породжується даним ЧА.

З даною метою, будемо подавати на вхід часткового автомату, приведеного завчасно до початкового стану, різноманітні вхідні слова.

Подаючи чергову лiтеру х(к) = х_ік  на вхід ЧА, можна зіштовхнутися з ситуацією, коли відповідний їй вихідний сигнал не визначено.

Домовимось називати відповідне слово забороненим для даного ЧА.

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

1.4.3 Відображення, що породжується частковим автоматом, еквiвалентнi частковi автомати

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

Образ φ(р) будь-якого допустимого слова р при даному відображенні визначається так само, як і для повністю визначених абстрактних автоматiв.

Два часткових автомати з однаковими вхідними та вихідними  алфавітами називають еквівалентними, якщо породжувані ними часткові відображення мають одну й ту ж саму область визначення та співпадають на даній області.

1.4.4 Часткове відображення, що продовжує iнше часткове вiдображення, еквівалентне продовження часткового автомату

Часткове відображення (ЧВ) φ продовжує часткове вiдображення ψ, якщо область визначення часткового вiдображення φ включає в себе область визначення М часткового вiдображення ψ, і на області М обидва відображення співпадають.

Частковий автомат А називають еквівалентним продовженням частко-вого автомату В, якщо те часткове вiдображення, що породжує частковий авто-мат А , продовжує часткове вiдображення, що породжує частковий автомат В.

1.4.5 Початкові відрізки вхідного слова часткового автомату, умова повноти часткового вiдображення

Із визначення допустимих слів (для будь-якого часткового автомату А) випливає наступне: якщо вхідне слово р= х_і1. . . . . х_ік є допустимим, то допустимими будуть усі слова виду х_і1, х_і1х_і2,  . . ., х_і1…х_ік-1, якi називають початковими відрізками слова р (за визначенням, до початкових відрізків слова р відносять саме слово р і порожнє слово е, що не містить жодної лiтери).