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

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

2.2]

ТАБЛИЦА ПЕРЕХОДОВ

общая таблица переходов

таблица 2.1

в клетках таблицы помещаются значения из множества

в клетках таблицы помещаются значения из множества

....

{Ol, 02, .

. •. On}

ветственно. эти подтаблицы имеют общий основной столбец) (левый крайний столбец), в котором перечислены все возможные состояния в настоящий момент s; столбцы в обеих подтаблицах озаглавлены одинаково, причем каждому возможному значению входного символа в настоящий момент д; соответствует в каждой подтаблице свой столбец. таким

образом, строки обозначены символами О], 02..... о„.

а столбцы символами 1, I2.....р- клетке на пересечении строки О; и столбца Ij в подтаблице z помещается значение (Ij, О;) (это значение будем называть значением z), а в подтаблице s помещается значение fsilj, О;) (это значение будем называть значением s{). символы, записанные в клетках подтаблиц z и s, принадлежат выходному алфавиту z и множеству состояний 5 соответственно или подмножествам этих множеств. если д и д - характеристические функции детерминированного полностью определенного автомата, то эти функции должны быть однозначно определены для каждой упорядоченной пары (л;.,, s), где принадлежит множеству X, а - множеству 5. следовательно, подтаблица z должна содержать в каждой клетке

) основной столбец представляет собой перечень наименований, расположенных в крайнем левом столбце таблицы. строку, в которой в основном столбце стоит «К» (или в которой содержимое основного столбца есть «к»), обычно будем называть «строкой К».



ТОЧНО один элемент из Z, а подтаблица s - точно один элемент из S.

Хотя описательные обозначения состояний (выбираемые так, как в примерах § 1.7) являются полезными для интуитивного понимания роли .различных состояний при определении соотношений вход - выход и для определения функций Д и Д по словесному описанию системы, они становятся бесполезными после того, как эти функции определены. Поэтому в таблице переходов первоначальные обозначения можно заменить любыми другими, удобными для исследователя. В большинстве примеров, приводимых в книге, состояния будут обозначаться просто цифрами 1, 2, 3 и т. д.

Для иллюстрации построения таблицы переходов приведена таблица 2.2, которая представляет собой таблицу переходов системы, описанной в примере 2 § 1.7. Эта система названа автоматом Л1, а состояния «новое слово», «ждать нового слова», «появление и», «появление и-п» и «появление u-n-d» обозначены цифрами 1, 2, 3, 4 и 5 соответственно. Содержимое клеток таблицы представляет собой числовое отражение словесных доводов, объясняющих

Таблица 2.2

Автомат А\

выбор множества состояний в примере 2. Сравнение словесного описания с таблицей переходов позволяет оценить точность и краткость последней по сравнению с первым способом описания.



23] ПЕРЕЧИСЛЕНИЕ АВТОМАТОВ 37

2.3. перечисление автоматов

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

Класс (п, р, д)-автоматов. (я, р, д)-автомат - это

автомат, имеющий множество состояний s={ai, .....о„),

входной алфавит, определяемый множеством X = • •

Ip), и выходной алфавит, определяемый множеством

z={Ci, .....q] или некоторым подмножеством z. любая

таблица переходов, имеющая в основном столбце символы

О;, .....а„, заглавия столбцов i, I2.....Ip- значения

из можества z или из подмножества z и значения s из множества S, характеризует (л, р, д)-автомат. мощность

р, д ЭТОГО класса автоматов определяется формулой

Nn,p,, = {qnr. (2.1)

Класс явно минимальных (п, р, д)-автоматов. назовем (л, р, 9)-автомат явно минимальным, если для каждого t и каждого ]Ф1 имеется по крайней мере одно k такое, что /г(1* i)fzi%,k j)- любая таблица переходов, в которой все строки в подтаблице z различны, характеризует

явно минимальный автомат. мощность /v„, этого класса равна

<л. = «" "Ш/--). (2.2)

где отрицательные значения Nn, p,q считаются равными нулю.



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