Дерево преемников

В дальнейшем под о-множеством автомата М будем понимать любое конечное множество состояний М; элементы σ-множества не обязательно различны[24]. σ-множество, содержащее единственный элемент, называется простым; σ-множество, содержащее два или более одинаковых элементов, называется кратным; о-множество однородно, если все его элементы одинаковы (простое σ-множество является частным случаем однородного σ -множества).

Для автомата, у которого множество допустимых начальных состояний имеет мощность m, A-группа есть множество σ -множеств, причем т есть общее число элементов во всех входящих в A-группу σ -множествах. Число σ -множеств в A-группе называется решением группы. Решение A-группы не может превышать m. A-группа называется простой, если все σ -множества в ней просты; A-группа однородна, если все σ -множества в ней однородны.

Предположим, что G есть A-группа, содержащая σ -множества g₁, g₂, .., g_r. ξi₁, ξi₂, ..., ξi_l -преемник G есть другая A-группа, построенная согласно следующим правилам: (1) Разбиваем каждое множество g_i на подмножества такие, что два состояния gt включаются в одно и то же подмножество, если и только если они вырабатывают одинаковые реакции на входную последовательность ξi₁, ξi₂, ..., ξi_l. Считаем каждое подмножество как σ -множество, а множество всех таких σ -множеств—как A-группу, обозначенную через G'. (2) В σ - множествах из G' заменяем каждое состояние его преемником относительно входной последовательности ξi₁, ξi₂, ..., ξi_l. . Получаемая в результате A-группа есть ξi₁, ξi₂, ..., ξi_l -преемник G.

Дерево преемников есть структура, определенная для данного автомата М и заданного множества допустимых начальных состояний A (M). Структура состоит из ветвей, расположенных в последовательных уровнях, причем высшим уровнем является «нулевой» уровень, следующим за высшим является «первый» уровень и так далее. Нулевой уровень дерева содержит единственную ветвь, называемую начальной ветвью. В дереве преемников, построенном для автомата с входным алфавитом { ξ₁, ξ₂, ..., ξ_p}, каждая ветвь в k-м уровне (k ≥ 0) расщепляется на р ветвей, представляющих ξ₁, ξ₂, ..., ξ_p соответственно и являющихся ветвями в (k+1)-м уровне. Ветвь, представляющая входной символ ξ_i, называется «ветвь ξ_i». Ясно, что k-й уровень дерева содержит p^k ветвей. Последовательность из l ветвей таких,.что k-я ветвь находится в k-м уровне (k = 1, 2, ..., l), и таких, что (k + 1)- я ветвь порождается k-й ветвью (k = 1, 2, ...,l—1), называется путем по дереву; l называется длиной пути по дереву. Если k-я ветвь этого пути по дереву есть ξi_k, (k=1, 2, ..., l), то говорят, что этот путь описывает входную последовательность ξi₁, ξi₂, ..., ξi_l. Таким образом, первые k + 1 уровней дерева преемников содержат р^k путей, описывающих все возможные рк входные последовательности длины k, которые могут быть построены из р входных символов.

Каждая ветвь в дереве преемников, построенном для М и А(М), связана с A-группой. A-группа, с которой связана начальная ветвь, есть А(М). Если ветвь b связана с A-группой G, то ветвь ξ_i, которую порождает b, связана с ξ_i -преемником G. Таким образом, A-группы, связанные с ветвями k-го уровня (k ≥ 1), могут быть определены из A-групп, связанных с ветвями (k — 1)-го уровня. В этом методе любой уровень дерева может быть построен на основании построенного уровня, который непосредственно предшествует ему. Говорят, что путь по дереву ведет в A-группу G, если его последняя ветвь связана с G.

 

Рис. 4.6 показывает первые четыре уровня дерева преемников, построенного для автомата Л17 (рис. 4.3) и множества допустимых начальных состояний {2, 3, 4, 5}. Каждая

ветвь отмечена входным символом, который она представляет, и A-группой, с которой она связана. A-группа, связанная с начальной ветвью, есть множество допустимых начальных состояний {2, 3, 4, 5}. Остальные A-группы могут быть найдены с помощью таблицы или диаграммы переходов для A17. Например, когда а прикладывается к состояниям 2, 3, 4 и 5, выходные символы будут 0, 0, 1 и 1 соответственно и следующие состояния будут 1, 5, 3 и 2 соответственно; тогда а-преемник A-группы {2, 3, 4, 5) состоит из σ-множеств {1, 5} и {3, 2}. Следовательно, ветвь а в первом уровне дерева преемников связана с A-группой {1,5}, {3, 2).

Следующие леммы, которые описывают некоторые свойства дерева преемников для автомата М и множества допустимых начальных состояний А(М), являются прямыми результатами вышеприведенных правили определений.

Лемма 4.1. Пусть через А (М) обозначено G₀ и пусть G_k есть А-группа, связанная с k-й ветвью пути по дереву. Тогда: (а) Решение G_k равно или превышает решение G_k-1. (б) Если G_k-l содержит кратное σ-множество, то G_k также должно содержать кратное σ-множество.

Лемма 4.2. Пусть А (М) = {σi₁, σi₂, .., σi_m} и пусть G есть А-группа, к которой ведет путь по дереву, описывающий входную последовательность ε. Пусть σ´i_k обозначает преемника σi_k по отношению к ε. Тогда: (а) σ´i₁, σ´i₂, .., σ´i_m —это m состояний, содержащихся в σ-множествах G. (б) σ´i_k и σ´i_l, находятся в различных , σ-множествах G тогда и только тогда, когда σi_k и σi_l выдают различные выходные последовательности при подаче входной последовательности ε.

Лемма 4.3. Пусть b₁ и b₂ обозначают две ветви, связанные с одинаковыми А-группами. Тогда ветвь, связанная с А-группой G, может быть достигнута из b₁

через l ветвей тогда и только тогда, когда ветвь, связанная с А-группой G, может быть достигнута из b₂ через l ветвей.