Реферат Побудова кодопреобразователя

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

Виняток недосяжних станів.

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

В 

Визначення класу сумісності.

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

Стани називаються i-сумісними для i = 1, 2, ..., якщо результат застосування до цих станів будь-якого слова довжини i буде однаковим. Класи сумісних станів можуть бути знайдені безпосередньо за таблицею виходів. В один і той же 1 - клас зараховуються стани, що позначають збігаються (з точністю до невизначених вихідних сигналів) стовпчики таблиці виходів. Класи (i +1) - сумісності виходять з класів i - сумісності шляхом їх розщеплення на класи (i +1) - сумісності. Для цього у кожного стану, що належить j - класу i - сумісності C j (i), номери класів (індекси), в які автомат переходить під впливом кожної вхідної літери. Якщо номер класу не визначений, то ставиться спеціальний символ, наприклад, прочерк. Індекси класів, в які переходить автомат під впливом вхідного сигналу, утворюють позначку. Безліч станів з однаковими відмітками в класі C j (i) утворюють класи (i +1) - сумісності. При виконанні операції розщеплення класів спеціальний символ невизначеності може бути замінений номером (індексом) будь-якого класу. Якщо операцію розщеплення i-класів застосувати послідовно, починаючи з 1-класу, то через кінцеве число кроків процес розщеплення закінчиться. Нерозщеплюваних далі класи утворюють класи сумісних станів. Іноді позначки станів різних класів збігаються, але об'єднувати такі стану в один клас (i +1) - сумісності абсолютно неприпустимо.

Завданням мінімізації методом розщеплення класів є отримання якомога меншої кількості і як можна більшої ємності класів кінцевої сумісності.

В 

Класи одиничної сумісності

У класи одиничної сумісності помістимо:

C 1 (1)

0

1

0

1

1

1

1

1

2

1

1

3

1

1

4

1

-

5

2

-

6

2

-

7

1

1

8

1

1

9

2

2

12

1

-

13

1

-

14

2

-

15

2

-

18

2

-

19

2

-

22

1

-

23

2

-

26

1

-

27

2