Введение в схемы, автоматы и алгоритмы



             

Недетерминированные конечные автоматы и их детерминизация


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

Определение 4.8. Недетерминированный конечный автомат (НКА) - распознаватель - это система вида

M = <\Sigma, Q, q_0, F, \Phi>,

включающая следующие компоненты:

  • ? ={a1, … , am} (m
    1) - конечное множество - входной алфавит;
  • Q={q0, … , qn-1} (n
    1) - конечное множество - алфавит внутренних состояний;
  • q0
    Q - начальное состояние автомата;
  • F
    Q - множество принимающих (допускающих, заключительных) состояний;
  • ?: Q ? (?
    {?})
    2Q - функция переходов.

Для a

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

Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары q

Q и a
? и каждого состояния q'
?(q, a) в программу помещается команда q a
q', и для каждого состояния q'
?(q, ?) в программу помещается команда q
q'. Отличие от детерминированного случая состоит в том, что для одной пары q
Q и a
? в программе может быть несколько команд вида q a
q' или не быть ни одной такой команды. Кроме того, могут появиться ?-команды (пустые переходы) вида q
q', означающие возможность непосредственного перехода из q в q' без чтения символа на входе.

При табличном задании функции ? в таблице появляется (m+1)-ый столбец, соответствующий пустому символу ? и на пересечении строки q и столбца a

(?
{?}) стоит множество состояний ?(q,a).

Для недетерминированного автомата M = <?, Q, q0, ? > в диаграмме DM=(Q, E) с выделенной начальной вершиной q0 и множеством заключительных вершин F ребра взаимно-однозначно соответствуют командам: команде вида q a

q' (a
?) соответствует ребро (q,q'), с меткой a , а команде вида q
q' соответствует ребро (q,q'), с меткой ?.




Содержание  Назад  Вперед