) Автором этого автомата является Хиббард (Т. N. Н I b b а г d, Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines, J. Assoc. Comput. Mach., vol. 8, pp. 601-612. 1961).

Таблица 4.14 демонстрирует регулярный условный эксперимент для Л17, показанного на рис. 4.3, и множества допустимых начальных состояний (1, 2, 3, 4, 5}, когда истинное начальное состояние есть 4. Первый столбец содержит для справки перечень состояний, через которые Л17 проходит по мере проведения эксперимента (эти состояния, конечно, не известны экспериментатору). В этом примере есть (1, 2, 3, 4, 5}, а 0 есть а. Когда а подается на Л17, наблюдаемая реакция есть 1, из которой может быть выведено, что gQ есть (4, 5}. Тогда g есть а-преемник g, а именно (3, 2}. Подача i = aa на Л17 дает реакцию 01, из которой может быть выведено, что g[ есть (3). Тогда g есть аа-преемник g, а именно (2). Так как g однородно, можно сделать заключение, что конечное состояние Л17 есть 2.

Рис. 4.17 показывает автомат, обозначенный М*, в котором могут быть достигнуты границы теоремы 4.131). Как показано на рисунке, множеством.состояний М* является

(1, 2.....п], входной алфавит есть I2.....In-i}> з

выходной алфавит-(О, 1}. Выходной символ 1 генерируется только тогда, когда подается в состоянии п. Из структуры УИ* можно увидеть, что если этот автомат, находясь в состоянии 1, 2...../, J (J> I), подвергается воздействию любого входного символа, отличного от y i, то состояниями-преемниками,

соответственно, являются 1,2.....I, j или 1,2.....I, j - 1.

По отношению к установочному дереву для М* и множеству

допустимых начальных состояний (1, 2.....т] под этим

понимается, что кратчайший путь, ведущий из (1, 2.....т]

к Л-группе, содержащей, по крайней мере, два а-множества, есть путь, описывающийся входной последовательностью im-ilm • • 1л-1> Л-группа, К которой ведет этот путь, есть 1, 2, .... т - 1}, [п]. Тогда по индукции кратчайший

путь, ведущий от (1, 2.....т] к однородной Л-группе,

есть путь, описывающийся входной последовательностью Im-ilm 1п-\ (длины Л -m + l), за которой следует lm-2lm-i ••• 1/1-1 (длины Л -/Я + 2).....за которой следует iilj ... (длины п-1). Длина этой последователь-

НОСТИ есть (2п- /я) (/я - 1)/2, т. е. совпадает с выражением (4.14). Путь ведет к Л-группе (1), [п]. {п], .... [п], которая содержит т простых (и, следовательно, однородных)

3 (ym(k,/o)i(yo]-i(„.,m

(Ш V(,/3J У(Ш V - V Ш\(уз;

(iiWi--vrf.,/; vrw; vr,.,/;

(ln-г/О)

Рис. 4.17. Автомат М*.

а-множеств. Рис. 4.18 показывает установочное дерево для автомата М* и множества допустимых начальных состояний {1, 2, от}; на этом рисунке все оконечные ветви опущены, и единственный показанный путь есть путь, описывающий минимальную установочную последовательность, упомянутую выше. Ясно, что если начальным состоянием М* оказалось состояние 1, то кратчайший условный установочный

flZ....] т-Г,т}

I т-Г

{1,2,...,m-/,m-rj n-mi-f ] t„

(7,2,...,/77-7, т*2} 1 п-г

{Г,2...., 777-7, 77/

fr,2,...,777-2,777-7},{77}

{7,2,..., 777-2, 777}, {/7}

у/7ое7/е/2 (7,2...., 777-777/J, М

{7,2,...,/77-2,77},{77}

{7,2,..., 777-3,-2}, {77}, {77}

{7.2},{77}....{77>

{7,2} {77}..., {77}

{7,4}{77}...,{П}

{7,77}{n}...,{n}

{7>.{П}{77},...,{Г7}

Рис. 4.18. Установочное дерево для М* и множества допустимых начальных состояний (1,2, ...,т).