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

[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]


Методом, описанным \ (ДХ,, в § 3.10, легко проверить, /

что Л16 = Л15. Таким образом, если мы не сумели Рис. 3.11. Автомат Л1б. обнаружить избыточности в

устном описании, мы все равно можем получить Л16 (с точностью до изоморфизма) применением к Л15 любой стандартной методики минимизации автоматов.

Попутно заметим, что роль, которую играет минимальная форма в теории конечных автоматов, аналогична роли, которую играет «эквивалентная схема Тевенена» в теории линейных цепей. Оба представления системы служат для описания ее поведения, наблюдаемого на доступных выводах, наиболее компактным способом.

3.13. Уменьшение числа состояний автомата последовательным объединением

Пусть М. - автомат, о котором известно, что его состояния О; и Оу эквивалентны. Объединением состояний О; и Оу

по правилам объединения эквивалентных состояний при минимизации, описанным в § 3.11, мы можем получить другой автомат Ni. При этом состояния о,- и Оу заменяются одним состоянием, скажем оу, которое переходит в то же состояние, что и О; (или Оу), и вырабатывает такой же выходной символ, как и (или Оу), при приложении одного и того же ВХОДНОГ0 символа. Это значит, что оу эквивалентно о и Оу и, следовательно. Ж] = Ж. Далее, если известно, что в М. имеются два эквивалентных состояния, то, повторяя описанную

состояний:

= {Г, Ц), Z={1, 0}. 5= {Г, Ц),

где указанные два состояния отождествляются со всеми возможными исходами при (v-1)-м подбрасывании. В результате получим граф переходов для автомата Л16, изо- ШМ (и/щ (f/V браженный на рис. 3.11.



операцию объединения, можно получить Alj = Ж]. Эта процедура может повторяться до тех пор, пока не будет получен М= М 1, не имеющий эквивалентных состояний. Обозначая исходную форму автомата М через Mq, можно установить, что M{k~l), полученный с помощью описанной процедуры, всегда меньше и, следовательно, представляет собой сокращенную форму М.

Сокращение автомата последовательным объединением особенно удобно, когда рассматриваемый автомат имеет явно эквивалентные состояния, которые могут быть отмечены при рассмотрении таблицы переходов. Поскольку, согласно теореме 3.1, явно эквивалентные состояния являются эквивалентными, то для сокращения заданного автомата они могут быть объединены, как описано в предыдущем абзаце. Объединение двух явно эквивалентных состояний, скажем и Oj, наиболее удобно выполнять по таблице переходов, вычеркивая строку Oj и заменяя всюду в подтаблице si обозначение «Оу» на «О;».

В качестве примера приведены таблицы 3.16 - 3.19, в которых даны последовательные стадии сокращения автомата Л6, изображенного на рис. 3.1 и в таблице 3.1. Для удобства таблица 3.1 воспроизведена здесь еще раз как таблица 3.16. В этой таблице пары состояний {1,5} и {2,6} являются явно эквивалентными; вычеркивая строки 5 и 6 и

Таблица 3.17 Автомат j46i

лица

3.16

Автомат AQ

s \

s \



заменяя каждое из обозначений «5» на «1» и каждое «6» на «2», получим автомат Л6]=Л6, представленный таблицей 3.17.

Таблица 3.18 Автомат А2

Таблица 3.19 Автомат Лвз

S \

•S \

V \

В Лб; пара состояний {3,7} является явно эквивалентной; вычеркивая строку 7 и заменяя каждое обозначение «7» на «3»,


(г/О



(y/zj

Рис. 3.12. Автомат Лб.

получаем автомат Лб2=Лб1, представленный таблицей 3.18. В Л62 явно эквивалентной является пара {4,8}. Вычеркивая строку 8 и заменяя каждую цифру «8» на «4», получим автомат АЪ= Л62, представленный таблицей 3.19. Поскольку



[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.0011