частковий автомат
Частковим автоматом називається абстрактний автомат, у якого функція переходів або функція виходів (звичайна або зрушена), або обидві ці функції, визначені не для всіх пар значень своїх аргументів а їх. [1]
Беручи відповідний частковий автомат. де ці переходи і виходи не визначені зовсім, ми тим самим залишаємо за собою право визначити їх згодом так, як це нам буде зручно. [2]
Для часткових автоматів вживаються ті ж способи завдання, що і для цілком певних автоматів. У тих місцях таблиці переходів або таблиці виходів (звичайною або зрушено), в яких зображувані ними функції не визначені, ми будемо ставити риски. Граф часткового автомата чможет мати вершини, з яких не виходять стрілки, позначені тими чи іншими вхідними сигналами. [3]
Для часткових автоматів Мура природно вважати забороненими їхні капітали, для яких зрушена функція виходів не визначена. Легко зрозуміти, що перейти з початкового стану в заборонене під впливом непорожньої слова автомат Мура може лише в тому випадку, коли це слово - заборонене. [4]
Для часткових автоматів Мілі і Мура в розглянутих таблицях на місці невизначених станів і вихідних сигналів ставиться прочерк. [5]
У разі часткових автоматів крім еквівалентності і ізоморфізму автоматів часто використовуються поняття еквівалентного і изоморфного продовження автоматів. [6]
Сутність завдання мінімізації часткових автоматів полягає в наступному: дана частковий автомат (Мура або Милі) А, що індукує часткове автоматне відображення ф, певне на деякій множині М слів вхідного алфавіту. Потрібно побудувати частковий автомат (Мура або відповідно Милі) У, який індукує часткове автоматне відображення, що збігається на множині М з відображенням ф, і має найменше число внутрішніх станів серед всіх автоматів (Мура або Милі), які відповідають цій умові. [7]
На відміну від часткових автоматів. які розглядалися раніше автомати називаються цілком певними. [8]
Для випадку ж часткових автоматів властивість транзитивності для відносини / - сумісності, взагалі кажучи, не виконується. [9]
У разі ж часткових автоматів все набагато складніше: з побудовою ос-класів і нормальної форми процес мінімізації, взагалі кажучи, не закінчується. [10]
Якщо функцію переходів довільного часткового автомата Мілі А розглядати не заданої у всіх точках, в яких не задана його функція виходів то що виник таким чином новий частковий автомат Мілі У буде, індукувати те ж саме часткове відображення, що і автомат А. [11]
Не зраджуючи индуцируемого частковим автоматом Мура часткового відображення, можна вважати функцію переходів цього автомата невизначеною щоразу, коли вона приймає заборонене значення. [12]
Подібно цілком певним автоматам часткові автомати також діляться на автомати першого і другого роду, автомати Мілі і автомати Мура. Ізоморфізм часткових автоматів передбачає, щоб відповідне изоморфное відображення переводило безлічі значень, в яких не визначені функції переходів або виходів (звичайна або зрушена) одного автомата, в безлічі значень, в яких не визначені відповідні функції іншого автомата. [13]
Відзначимо, що синтез часткових автоматів не відрізняється від викладеного вище. При тих комбінаціях вхідних сигналів і внутрішніх станів часткового автомата, які не входять до кодовані таблиці переходів і виходів, значення функцій збудження можна вибирати довільно. [15]
Сторінки: 1 2 3 4