А   Б  В  Г  Д  Е  Є  Ж  З  І  Ї  Й  К  Л  М  Н  О  П  Р  С  Т  У  Ф  Х  Ц  Ч  Ш  Щ  Ю  Я 


Таблиця - перехід - автомат

Таблиця переходів автомата Мура в загальному випадку може бути багатозначною для декількох вхідних векторів. Як окремий випадок, вона може бути багатозначною і для всіх своїх вихідних векторів. І в цьому випадку відновити автомат Мура можливо, ставлячи у відповідність кожному новому з'явився станом кінцевий набір вхідних і вихідних векторів.

Правило побудови таблиці переходів автомата полягає в наступному.

використовуючи табл. III.5 і таблицю переходів автомата А (табл. III.1), легко побудувати (векторну) функцію збудження автомата А. Позначимо через х - (х) зовнішній структурний вхідний сигнал автомата А; через v - (PI I) - структурний вихідний сигнал цього автомата, а через і (ul иг) - структурний вхідний сигнал його пам'яті.

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

Другий крок полягає в побудові таблиці переходів шуканого автомата А. При цьому вхідними сигналами служать букви вихідного алфавіту Ж, а внутрішні стану автомата ототожнюються з множинами основних індексів.

Граф автомата Мілі (а і граф автомата Мура (б. В деяких випадках виявляється зручним замість таблиці переходів автоматів Мілі і Мура використовувати так звану квадратну автоматну таблицю. Квадратної автоматної таблицею називається таблиця, у якій рядки і стовпці позначені різними станами автомата. Xk, кожен з яких викликає перехід автомата зі стану Л /в стан Л /, позначається шляхом об'єднання сигналів знаком диз'юнкції: Х V з V V Xk. Для позначення порожнього безлічі може використовуватися риска.
 Виробляючи перекодування станів і вихідних букв, отримуємо зазначену таблицю переходів автомата.

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

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

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

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

Еквівалентну перетворення автоматів Мура, яке встановлюється пропозицією 1.7 зводиться до того, що в таблиці переходів автомата Мура символи заборонених станів замінюються рисками.

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

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

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

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

У разі необхідності знайдений автомат Мура інтерпретується як автомат Мілі В. Таблиця переходів автомата А при цьому приймається за таблицю переходів автомата В, а таблиця виходів автомата У виходить в результаті підстановки в його таблицю переходів замість символів станів символів, які відзначають ці стану вихідних сигналів (відміток ) автомата А.

Вхідні сигнали автомата також передбачаються закодованими в двійковій структурному алфавіті. замінюючи в таблиці переходів автомата кожне його структурний (закодоване) стан структурним вхідним сигналом пам'яті автомата, що викликає вказаний в таблиці перехід, ми приходимо до поняття таблиці збуджень автомата. За нею, а також щодо структурної таблиці виходів автомата безпосередньо будується його функціональна таблиця (див. § 2), що є вихідним пунктом для побудови комбінаційної частини схеми даного автомата.

Для реалізації УА на основі моделі автомата Мілі необхідно побудувати його таблицю переходів. Для цього в таблиці переходів автомата Мура (табл. 5.1) об'єднаємо ті стану автомата Мура, переходи з яких повністю збігаються.

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

У разі необхідності знайдений автомат Мура інтерпретується як автомат Мілі В. Таблиця переходів автомата А при цьому приймається за таблицю переходів автомата В, а таблиця виходів автомата У виходить в результаті підстановки в його таблицю переходів замість символів станів символів, які відзначають ці стану вихідних сигналів (відміток) автомата А.

Розглянемо тепер метод отримання функцій збудження елементарних автоматів і функцій виходів по графу автомата або по матриці з'єднань. Ця методика менш громіздка, ніж побудова функцій збудження по кодованої таблиці переходів автомата в разі канонічного методу синтезу, і дуже зручна для переходу від етапу абстрактної декомпозиції до функціональній схемі автомата.

Розбиття на 1-класи відбувається безпосередньо по таблиці виходів автомата: в один і той же 1-клас об'єднуються всі стани, яким відповідають однакові стовпці в таблиці виходів. Далі будується так звана 1-таблиця, що виходить в результаті заміни в таблиці переходів автомата, внутрішніх станів містять їх 1-класами.

Перший стовпець таблиці позначимо символом 1 початкової вершини графа і з неї починаємо побудова таблиці переходів автомата. На початку побудови таблиці в стан qj входить один індекс початкової вершини. Якщо таких стрілок немає, в клітку вписується - - символ порожнього стану автомата. Після заповнення клітин стовпця таблиці вміст кожної клітини, якщо воно повністю не збігається з вмістом станів, які відзначають стовпці, виписується як нове що відзначає стан. Процес побудови таблиці переходів вважається закінченим, якщо весь вміст кожної клітини таблиці виписано як що відзначає стан.

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

Там, де завдання розмальовки ускладнена додатковими умовами однобарвності вершин, ефективним може виявитися і підхід, що передбачає знаходження найбільшого порожнього або повного подграфа, а потім групування близько вершин, які увійшли в цей підграф, інших вершин заданого графа. За допомогою цього підходу, як показано в[26], Можна вирішити такі завдання, як мінімізація довжини коду станів асинхронного автомата, стиснення таблиці переходів автомата (по рядках і стовпцях), паралельна декомпозиція автомата, спрощення системи булевих функцій, що описують асинхронний автомат. Точно так само можна вирішувати і всі інші завдання, перераховані вище. З розглянутих тут підходів до вирішення завдань логічного проектування даний підхід єдино придатний для вирішення таких завдань абстрактного синтезу автоматів, як мінімізація числа станів синхронного автомата і його декомпозиція.

Невизначеними в цьому випадку будуть все вихідні сигнали, до складу яких входить символ області заборони S. Невизначені станухарактеризуються за допомогою пропозиції 7.2. Зокрема, для автоматів Мура невизначеними будуть їхні капітали, відмічені невизначеними вихідними сигналами. Початковий стан є невизначеним, якщо воно не входить в число елементів таблиці переходів автомата.

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

Граф функціонування цифрового автомата.

Цифровий автомат має повну системою переходів, якщо для кожної пари його внутрішніх станів wt і Wj знайдеться хоча б один вхідний сигнал, який переводить автомат з стану ш, в стан Wj. Ця умова має виконуватися як при i. Інакше кажучи, для повноти системи переходів необхідно і достатньо, щоб для будь-якої пари станів Wi і Wj рівняння Wj ty (Wi u) дозволялося щодо і. При виконанні цієї умови в кожному стовпчику таблиці переходів автомата обов'язково повинні фігурувати символи всіх його станів.

Суть явища гонок полягає в наступному: елементи затримки, що їх вживають в схемі в якості запам'ятовуючих елементів, мають різні (хоча зазвичай і досить близькі один одному) часи спрацьовування. Різні також затримки сигналів (тобто довжини передніх фронтів), що надходять на вхідні канали елементів затримки по логічним ланцюгах, які мають неоднакову довжину. Якщо за умовами спрацьовування (таблиці переходів) автомата в якийсь момент часу повинні змінити свій стан відразу кілька запам'ятовуючих елементів, то між елементами починаються гонки. Це, як неважко зрозуміти, може викликати перехід автомата зовсім не в той стан, який передбачено таблицею переходів автомата.

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