Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [ 81 ] [82] [83] [84] [85] [86] [87] [88]

7.»1 КВАЗИЭКВИВАЛЕНТНЫЕ АВТОМАТЫ 251

пустой (или заполняется прочерком). Тогда построение последующих вариантов таблиц пар состояний может быть выполнено таким же образом, как это описано в § 3.7. Не выделенные жирным шрифтом элементы столбца пар в конечном варианте таблицы пар представляют все совместимые пары состояний для данного автомата.

Например, таблица 7.2 представляет конечный вариант таблицы пар для автомата AZ2, изображенного на рис. 7.1. Из таблицы следует, что совместимыми парами в автомате Л32 являются: {1,2}. {1,3}, {1.5}. {2,3}. 2,4}, {2,5}, {3,5}. {3,6} и {4.6}.

7.3. Квазиэквивалентные автоматы

Говорят, что состояние Oj автомата М квазиэквива-лентно состоянию автомата М, если любая входная последовательность, допустимая для О;. вызывает одинаковые реакции при приложении ее к Жа, и М\а. Говорят, что автомат М квазиэквивалентен автомату М, если для каждого состояния автомата М имеется, по крайней мере, одно состояние Oj автомата М, такое, что Оу квазиэквива-лентно О;. На основе этого определения автомат М может быть интерпретирован следующим образом. Если дан неизвестный автомат, который может быть М или М, и известна реакция этого автомата на любую входную последовательность, допустимую для некоторого состояния автомата М, то нет способа определить, является неизвестный автомат автоматом М или М. Таким образом, М квазиэквивалентен М, если не существует способа отличить М от М при помощи внешних экспериментов, которые используют только те входные последовательности, которые допустимы для состояний автомата М, Заметим, что отношение квазиэквивалентности не является симметричным отношением; тот факт, что М квазиэквивалентен М, не означает, что М квазиэквивалентен М,

Пусть Sj, Sj, 2„ - множества состояний автомата М такие, что каждое состояние автомата М включено, по крайней

мере, в одно множество S. Множество множеств Sj, 1.....2„

называется группировкой; п называется мощностью группировки. Два состояния, которые находятся вместе, по крайней



мере, в одном множестве 2, составляют сопряженную пару; пара состояний, которая не является сопряженной, называется разобщенной парой. Группировка называется правильной, если она удовлетворяет двум следующим условиям: (1) реакции автомата Жа и л1о., где и о составляют любую сопряженную пару, на любой входной символ у, допустимый для и , одинаковы; (2) первые преемники состояний и о по отношению к у одинаковы или составляют сопряженную пару.

Пусть автомат М имеет множество состояний (О), Oj, .... а„}. Пусть автомат М квазиэквивалентен автомату М и имеет множество состояний aj, Oj, oj. По определению квазиэквивалентности каждому состоянию о,- автомата М должно соответствовать, по крайней мере, одно состояние автомата М, которое квазиэквивалентно о. Распределим состояния автомата М по множествам Sj, ..... S„ таким, что

2; - множество всех состояний, по отношению к которым 0 квазиэквивалентно. Эти множества составляют группировку, так как они включают каждое состояние М, по крайней мере, один раз. Пусть и -произвольная пара состояний из 2; и пусть у - любой символ, допустимый для и о,. Реакция М а, и Ж о, на , должна быть такой же, как и реакция М\а[ на Поэтому реакции Ж[а. и /Иа на у должны быть одинаковы. Предположим, что первыми преемниками состояний и по отношению к у являются и и что первый преемник состояния а\ по отношению к l,j есть al. Так как а[ квазиэквивалентно а и , то должно быть квазиэквивалентно а и о. Поэтому а и не могут быть разобщенными и должны принадлежать

одному и тому же множеству 2. В заключение можно сделать вывод, что группировка 2,, 22, 2„ автомата М, построенная описанным выше способом, должна быть правильной группировкой.

Если дан автомат М с правильной группировкой 2;, Sj, .... 2„, то автомат М может быть построен по следующие правилам. М имеет я состояний, обозначаемых



7.3] КЁАЗИЭКВИВАЛЕНТНЫЕ АВТОМАТЫ 253

Oj, Oj, о. Если состояние М, принадлежащее множеству 2„, переходит в состояние, принадлежащее множеству \, и при этом выдается выходной символ с* при входном символе у, то в М состояние переходит в и при этом выдается выходной символ с* при приложении входного символа Ij. Никакой неоднозначности при таком построении не получается, так как, если некоторое состояние автомата М, принадлежащее 2, переходит в некоторое состояние, принадлежащее 2,, и при этом выдается выходной символ на входной символ у, то каждое состояние М, которое принадлежит 2„ и для которого допустим символ Ij, переходит в состояние, которое принадлежит 2,, и при этом выдается символ на входной символ у. Из построения М следует, что состояние а, автомата М квазиэквивалентно

каждому состоянию М, принадлежащему множеству 2. Поэтому автомат М квазиэквивалентен автомату М. Таким образом, имеем следующий результат.

Теорема 7.1. Каждому автомату М! с п состояниями, который квазиэквивалентен автомату Ж, соответствует в Ж правильная группировка мощности п. Каждой правильной группировке мощности п в автомате Ж соответствует автомат Ж, который квазиэквивалентен автомату Ж.

Построение правильной группировки автомата Ж при заданном Ж и построение Ж при заданной правильной группировке автомата Ж можно осуществить так, как это описано выше. Если Ж - автомат с г состояниями и если л < г, то говорят, что Ж - сокращенная форма Ж. Если не существует сокращенной формы Ж, имеющей меньше чем п состояний, то говорят, что Ж - минимальная форма Ж, которая обозначается Ж. Минимальная форма Ж данного автомата Ж имеет такое же значение для автоматов с ограничениями на входе, как и для автоматов без ограничений на входе: Ж - наименьший автомат, который ведет себя так же, как заданный автомат Ж. Однако следует иметь в виду, что в случае автомата с ограничениями на входе поведение автоматов М и М сравнимо только в отношении входных последовательностей, допустимых для состояний исходного автомата Ж.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [ 81 ] [82] [83] [84] [85] [86] [87] [88]

0.0015