Недетерминированные конечные автоматы

Определение:

Недетерминированный конечный автомат (НКА) — пятерка [math]\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle[/math], где [math]\Sigma[/math] — алфавит, [math]Q[/math] — множество состояний автомата, [math]s[/math] — начальное состояние автомата, [math]T[/math] — множество допускающих состояний автомата, [math]\delta[/math] — функция переходов. Таким образом, единственное отличие НКА от ДКА — существование нескольких переходов по одному символу из одного состояния.

Процесс допуска

Определение:

Мгновенная кофигурация — пара [math] \langle p, q \rangle [/math], [math] p \in Q [/math], [math] q \in \Sigma^*[/math].

Определим некоторые операции для мгновенных конфигураций.

Определение:

Говорят, что [math] \langle p, \beta \rangle[/math] выводится за один шаг из [math]\langle q, \alpha \rangle [/math], если: [math]\alpha = c\beta[/math]; [math]p \in \delta (q, c)[/math]. Это также записывают так: [math]\langle q, \alpha \rangle \vdash \langle p, \beta \rangle[/math].

Определение:

Говорят, что [math] \langle p, \beta \rangle[/math] выводится за ноль и более шагов из [math]\langle q, \alpha \rangle [/math], если [math]\exists c_1, c_2 \ldots c_n[/math]: [math]\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \vdash \langle u_{n-1}, c_n \beta\rangle \vdash \langle p, \beta \rangle[/math] Это также записывают так: [math]\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle[/math].

Определение:

НКА допускает слово [math]\alpha[/math], если [math]\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle[/math].

Менее формально это можно описать так: НКА допускает слово [math] \alpha [/math], если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово [math] \alpha [/math].

Язык автомата

Определение:

Множество слов, допускаемых автоматом [math] \mathcal{A} [/math], называется языком НКА [math] \mathcal{A} [/math]. [math] \mathcal{L}(\mathcal{A}) = \lbrace w | \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace [/math].

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

Пример

Это НКА, который распознает язык из алфавита [math] \lbrace 0, 1 \rbrace [/math], где на четвертой с конца позиции стоит 0.

Алгоритм, определяющий допустимость автоматом слова

Постановка задачи

Пусть заданы НКА и слово [math]w[/math]. Требуется определить, допускает ли НКА данное слово.

Алгоритм

Определим множество всех достижимых состояний из стартового по слову [math] \alpha [/math] : [math] R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace [/math].

Заметим, что если [math] \exists t \in T : t \in R(w) [/math], то слово допускается, так как [math] \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle [/math] по определению [math] R(w) [/math]. Таким образом, алгоритм состоит в том, чтобы построить [math] R(w) [/math].

Очевидно, что [math] R(\varepsilon) = \lbrace s \rbrace [/math]. Пусть мы построили [math] R(\alpha) [/math], построим [math] R(\alpha c)[/math], где [math] c \in \Sigma [/math]. Заметим, что [math] R(\alpha c) = \lbrace q | q \in \delta(p, c), p \in R(\alpha) \rbrace [/math], так как

[math] \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle p, c \rangle \vdash \langle q, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle q, \varepsilon \rangle [/math], [math] \forall q \in \delta(p, c) [/math].

Теперь, когда мы научились по [math] R(\alpha) [/math] строить [math] R(\alpha c)[/math], возьмем [math] R(\varepsilon) [/math] и будем последовательно вычислять [math]R(w[1]\ldots w[k])[/math] для [math]k=1..|w|[/math].

Таким образом, мы получим [math]R(w)[/math], и всё что осталось — проверить, есть ли в нём терминальное состояние.

Псевдокод

[math] R_0 = \lbrace s \rbrace [/math]
for i = 1 to length(w) do
   [math] R_i = \varnothing [/math]
   for [math] p \in R_{i - 1} [/math] do
       [math] R_i = R_i \cup \delta(p, w[i]) [/math]
accepts = False
for [math] t \in T [/math] do
   if [math] t \in R_{|w|} [/math]
      accepts = True

Время работы алгоритма: [math] \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) [/math].

См. также

• Детерминированные конечные автоматы
• Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Литература

• Ю. Громкович — Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию : Пер. с нем. — издательство БХВ-Петербург, 2010. — 336 с. : ISBN 978-5-9775-0406-5