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

Наведенi визначення дозволяють сформулювати твердження: область визначення М будь-якого часткового відображення, що породжується частковим автоматом, задовольняє умові повноти: разом iз будь-яким словом області М, дана область також містить усі початкові відрізки вказаного слова.

1.4.6 Автоматні відображення, умови автоматності вiдображень

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

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

1) автоматне вiдображення здійснює однозначне відображення (взагалі кажучи, часткове) множини слів в деякому скінченному алфавіті х (вхідному алфавітi автоматного вiдображення) у множину слів в деякому скінченному алфавіті у (вихідному алфавітi автоматного вiдображення);

2) область визначення автоматного вiдображення вiдповiдає умові повноти; за визначенням, порожнє слово завжди входить до областi визначення автоматного вiдображення;

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

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

1.4.7 Теорема Хоффмена-Мілі

Теорема Хоффмена-Мілі: якщо автоматне відображення φ вiдповiдає чотирьом умовам автоматності, то можна побудувати абстрактнi автомати Мілі та Мура (взагалі кажучи, нескінченні), що продовжують дане автоматне вiдображення; якщо область визначення відображення φ є скінченною, то абстрактнi автомати Мілі та Мура також можуть бути побудовані скінченними.

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

1.4.8 Обмеження, накладенi умовами автоматності на клас відображень, породжених частковим автоматом, операції вирівнювання слів i поповнення

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

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

1.5 Способи задавання автоматних вiдображень, поняття подiї, канонiчна множина подiй, алгебра подiй

1.5.1 Способи задавання автоматних вiдображень

Можна задавати автоматне вiдображення автоматом, який його породжує.

Але на практиці, при постановці задач синтезу автоматiв, даний спосіб задавання є кінцевою метою, а не початковим етапом.

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

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

У результаті, отримують так звану скорочену таблицю виходiв.

Інколи за допомогою таблиць можна завдавати автоматнi вiдображення з нескінченною областю визначення.

Найбільш поширеним способом задавання довільного автоматного вiдображення є його задавання за допомогою автоматної множини подій.

1.5.2 Подія в довільному алфавіті; подія, представлена в автоматному вiдображеннi лiтерою вихідного алфавіту; канонічна множина подій