Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

В дальнейшем под -множеством автомата М будем понимать любое конечное множество состояний ; элементы -множества не обязательно различны -множество,

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

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

Предположим, что О есть А-группа, содержащая -множества -преемник О есть другая А-группа, построенная согласно следующим правилам: (1) Разбиваем каждое множество на подмножества такие, что два состояния включаются в одно и то же подмножество, если и только если они вырабатывают одинаковые реакции на входную последовательность Считаем каждое подмножество как -множество, а множество всех таких -множеств — как А-группу, обозначенную через О. (2) В -множествах из О заменяем каждое состояние его преемником относительно входной последовательности Получаемая в результате А-группа есть - преемник О.

Дерево преемников есть структура, определенная для данного автомата М и заданного множества допустимых начальных состояний Структура состоит из ветвей, расположенных в последовательных уровнях, причем высшим уровнем является «нулевой» уровень, следующим за высшим является «первый» уровень и так далее. Нулевой уровень дерева содержит единственную ветвь, называемую начальной ветвью. В дереве преемников, - построенном для автомата с входным алфавитом каждая ветвь в уровне расщепляется на ветвей, представляющих соответственно и являющихся ветвями в уровне. Ветвь, представляющая входной символ называется «ветвь Ясно, что уровень дерева содержит

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

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

Рис. 4.6. Дерево преемников для и множества допустимых начальных состояний

Рис. 4.6 показывает первые четыре уровня дерева преемников, построенного для автомата (рис. 4.3) и множества допустимых начальных состояний Каждая ветвь отмечена входным символом, который она представляет, и А-группой, с которой она связана. А-группа,

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

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

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

Лемма 4.2. Пусть и пусть G есть -группа, к которой ведет путь по дереву, описывающий входную последовательность Пусть обозначает преемника по отношению к Тогда — это m состояний, содержащихся в -множествах G. (б) находятся в различных -множествах G тогда и только тогда, когда выдают различные выходные последовательности при подаче входной последовательности

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

<< Предыдущий параграф Следующий параграф >>
Оглавление