томатного часу, t +1-наступний момент дискретного автоматного часу.
Поняття теорії графів
В
графен називають взаємозв'язок двох множин складаються з безлічі вершин і безлічі ребер, індукованих (пов'язаних) між собою.
Повний граф - це граф, який не має петель, кратності ребер, і всі його вершини пов'язані між собою.
неорієнтовані граф - граф, який не має вказівки напрямів ребер, при переході з однієї вершини в іншу.
Орієнтований (повний) граф - граф з ребрами, що вказують конкретний напрям при переході з однієї вершини в іншу.
Граф-дерево - це слабосвязанних граф, у якого якщо видалити одне ребро, то він розпадається на два графа.
Граф автомата - орієнтований зв'язний граф, вершини якого відповідають стані, а дуги - переходам між ними.
Теорія графів має великі додатки, так як мова теорії, з одного боку, очевидний, а, з іншого боку, зручний в нормальному дослідженні. При повному зображенні графа не всі деталі малюнка мають однакове значення, а саме геометричні властивості ребер (кривизна, довжина і т.д.) і розташування вершин на площині відносно один одного.
Дві вершини графа автомата а т і a s (початковий стан і стан переходу) з'єднуються дугою (ребром), спрямованої від а т у a s . Дузі (а т , a s ) графа автомата приписується вхідний сигнал х і вихідний сигнал у, якщо він визначений, і, в іншому випадку, ставиться прочерк. Якщо перехід автомата зі стану а т у стан a s відбувається під дією декількох вхідних сигналів, то дузі (a m , a s ) приписуються всі ці вхідні і відповідні вихідні сигнали.
При описі автомата Мура у вигляді графа вихідний сигнал y записується всередині вершини а т або поряд з нею, а вхідний сигнал х над дугою (ребром), яка демонструє перехід з одного стану в інший.
При описі автомата Милі у вигляді графа всередині вершини записується стан, в яке переходить автомат, а над дугою (ребром), яка демонструє перехід з одного стану автомата в інше, записується дріб, у чисельнику якого вказується вхідний сигнал, а в знаменнику - вихідний сигнал.
Для завдання функцій переходів і виходів побудуємо граф-дерево автомата Мура, а потім автомата Милі. При використанні табличного опису автомата Мура таблиці переходів автоматів Мілі та Мура співпадуть, а таблиця виходів автомата Милі вийде з таблиці переходів заміною a s символом вихідного сигналу. p> У технічних цілях використовуються тільки детерміновані цифрові автомати, в яких виконана умова однозначності переходів: - автомат, що знаходиться в деякому стані, під дією будь-якого вхідного сигналу не може перейти більш ніж в один стан. Стосовно до табличного способу завдання описи автоматів це означає, що в клітинах переходів/виходів вказується тільки по одному станом/вихідному сигналом. Стосовно до графічного способу завдання опису автоматів це означає, що у графі автомата з будь вершини не можуть виходити дві або більше дуги, відмічені одним і тим же вхідним сигналом.
Стійким станом автомата називається такий стан, що для будь-якого х , d (a m , x) = a s , має місце d (a s , x) = a s . Це означає, що якщо автомат перейшов у якийсь стан х , то вийти з цього стану може тільки під дією іншого сигналу.
Синхронним називається автомат, якщо він не є асинхронним і кожне його стан стійко.
Якщо деякої пари (a m , z f ) вихідний сигнал автомата не визначений, то для цієї пари не визначається і функція переходу, так як не визначено допустиме слово, яке здійснює перехід з цього стану.
В
Граф-дерево автомата Мура.
Для побудови графа-дерево автомата Мура використовуємо таблицю відповідності, доповнену до виконання умови автоматними. Після виконання умови автоматними граф-дерево прийме вигляд:
В
Два автомата з однаковими вхідним і вихідним алфавітами називаються еквівалентними, якщо після установки початкового стану їх реакції на будь-яке вхідне слово збігаються. Звідси витікає, що для будь-якого автомата Милі існує еквівалентний автомат Мура, та, назад, для будь-якого автомата Мура існує еквівалентний йому автомат Мілі. Таким чином, можливі взаємні трансформації автоматів.
В
Граф-дерево автомата Милі.
10
У ході етапу побудови кодопреобразователя здійснюється перетворення графа-дерево автомата Мура в граф-дерево автомата Милі. Для цього всі кінцеві стану автомата Мура замінюються нульовим станом. Граф-дер...
