Системное программное обеспечение. Лабораторный практикум - страница 31

где:

Q – конечное множество состояний автомата;

Σ – конечное множество допустимых входных символов (входной алфавит КА);

δ – заданное отображение множества Q·Σ во множество подмножеств P(Q)δ: Q·Σ → P(Q) (иногда δ называют функцией переходов автомата);

– начальное состояние автомата;

– множество заключительных состояний автомата.

Другим способом описания КА является граф переходов – графическое представление множества состояний и функции переходов КА. Граф переходов КА – это нагруженный однонаправленный граф, в котором вершины представляют состояния КА, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода КА. Если функция перехода КА предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'.

Недетерминированный КА неудобен для анализа цепочек, так как в нем могут встречаться состояния, допускающие неоднозначность, то есть такие, из которых выходит две или более дуги, помеченные одним и тем же символом. Очевидно, что программирование работы такого КА – нетривиальная задача. Для простого программирования функционирования КА M(Q,Σ,δ,q_>0,F) он должен быть детерминированным – в каждом из возможных состояний этого КА для любого входного символа функция перехода должна содержать не более одного состояния:

Доказано, что любой недетерминированный КА может быть преобразован в детерминированный КА так, чтобы их языки совпадали [3, 7, 26] (говорят, что эти КА эквивалентны).

Кроме преобразования в детерминированный КА любой КА может быть минимизирован – для него может быть построен эквивалентный ему детерминированный КА с минимально возможным количеством состояний. Алгоритмы преобразования КА в детерминированный КА и минимизации КА подробно описаны в [3, 7, 26].

Можно написать функцию, отражающую функционирование любого детерминированного КА. Чтобы запрограммировать такую функцию, достаточно иметь переменную, которая бы отображала текущее состояние КА, а переходы из одного состояния в другое на основе символов входной цепочки могут быть построены с помощью операторов выбора. Работа функции должна продолжаться до тех пор, пока не будет достигнут конец входной цепочки. Для вычисления результата функции необходимо по ее завершении проанализировать состояние КА. Если это одно из конечных состояний, то функция выполнена успешно и входная цепочка принимается, если нет, то входная цепочка не принадлежит заданному языку.