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

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


Содержание

[править] Процесс допуска

НКА допускает слово \alpha, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово \alpha. Теперь это опишем более формально.

Определение:
Мгновенное описание (англ. snapshot) — пара \langle p, q \rangle, p \in Q, q \in \Sigma^*.

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

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


Определение:
Рефлексивно-транзитивное замыкание отношения \vdash обозначается как \vdash^*.
И говорят, что \langle p, \beta \rangle выводится за ноль и более шагов (англ. yields) из \langle q, \alpha \rangle, если \langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle.


Определение:
НКА допускает (англ. accepts) слово \alpha, если \exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle.


[править] Язык автомата

Определение:
Множество слов, допускаемых автоматом \mathcal{A}, называется языком НКА \mathcal{A}.
  • L(\mathcal{A}) =  \lbrace w \ | \ \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace.
В этом случае также говорят, что автомат \mathcal{A} распознаёт (англ. recognize) язык L.


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

[править] Пример

Finite state machine 4.png

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

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

[править] Постановка задачи

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

[править] Алгоритм

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

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

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

\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, \forall q \in \delta(p, c).

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

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

[править] Псевдокод

bool accepts(\langle \Sigma, Q, s, T, \delta \rangle: Automaton, \mathtt{w}: String):
  R_0 = \lbrace s \rbrace
  for i = 1 to \mathtt{w}.length
     R_i = \varnothing
     for (q in R_{i - 1}) 
         R_i = R_i \cup \delta(q, \mathtt{w}[i])
  return R_{|\mathtt{w}|} \cap T \neq \varnothing

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

[править] См. также

[править] Источники информации

  • Ю. Громкович Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 2010. — С. 87. — ISBN 978-5-9775-0406-5
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages, and Computation. Second edition. P. 71. ISBN 0-201-02988-X
  • Wikipedia — Nondeterministic finite automaton
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты