Учебники

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

В NDFA для определенного входного символа машина может перейти в любую комбинацию состояний в машине. Другими словами, точное состояние, в которое перемещается машина, не может быть определено. Следовательно, он называется недетерминированным автоматом . Поскольку оно имеет конечное число состояний, машина называется недетерминированным конечным автоматом или недетерминированным конечным автоматом .

Формальное определение NDFA

NDFA может быть представлен 5-кортежем (Q, ∑, δ, q 0 , F), где –

  • Q – конечное множество состояний.

  • – это конечный набор символов, называемых алфавитами.

  • δ – функция перехода, где δ: Q × ∑ → 2 Q

    (Здесь набор мощности Q (2 Q ) был взят, потому что в случае NDFA из состояния может произойти переход к любой комбинации состояний Q)

  • q 0 – начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).

  • F – множество конечных состояний / состояний Q (F ⊆ Q).

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

– это конечный набор символов, называемых алфавитами.

δ – функция перехода, где δ: Q × ∑ → 2 Q

(Здесь набор мощности Q (2 Q ) был взят, потому что в случае NDFA из состояния может произойти переход к любой комбинации состояний Q)

q 0 – начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).

F – множество конечных состояний / состояний Q (F ⊆ Q).

Графическое представление NDFA: (так же, как DFA)

NDFA представлен орграфами, которые называются диаграммой состояний.

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

пример

Пусть недетерминированный конечный автомат будет →

  • Q = {a, b, c}
  • ∑ = {0, 1}
  • q 0 = {а}
  • F = {c}

Функция перехода δ, как показано ниже –

Современное состояние Следующее состояние для ввода 0 Следующее состояние для ввода 1
а, б б
б с а, с
с До нашей эры с

Его графическое представление будет следующим:

NDFA Графическое представление

ДФА против НДФА

В следующей таблице перечислены различия между DFA и NDFA.

DFA NDFA
Переход из состояния в одно конкретное следующее состояние для каждого входного символа. Следовательно это называется детерминированным . Переход из состояния может быть в несколько следующих состояний для каждого входного символа. Следовательно это называется недетерминированным .
Пустые строковые переходы не видны в DFA. NDFA разрешает переходы пустой строки.
Отклонение разрешено в DFA В NDFA откат не всегда возможен.
Требуется больше места. Требует меньше места.
DFA принимает строку, если она переходит в конечное состояние. NDFA принимает строку, если хотя бы один из всех возможных переходов заканчивается в конечном состоянии.

Акцепторы, классификаторы и преобразователи

Акцептор (Распознаватель)

Автомат, который вычисляет булеву функцию, называется акцептором . Все состояния акцептора либо принимают, либо отклоняют введенные ему входные данные.

классификатор

Классификатор имеет более двух конечных состояний и выдает один выход при его завершении.

преобразователь

Автомат, который производит выходные данные на основе текущего входа и / или предыдущего состояния, называется преобразователем . Преобразователи могут быть двух типов –

  • Мили Машина – выход зависит как от текущего состояния и текущего ввода.

  • Moore Machine – Выход зависит только от текущего состояния.

Мили Машина – выход зависит как от текущего состояния и текущего ввода.

Moore Machine – Выход зависит только от текущего состояния.

Приемлемость DFA и NDFA

DFA / NDFA принимает строку, если DFA / NDFA, начиная с начального состояния, заканчивается после полного чтения строки в состоянии принятия (любом из конечных состояний).

Строка S принимается DFA / NDFA (Q, ∑, δ, q 0 , F), если

δ * (q 0 , S) ∈ F

Язык L принятый DFA / NDFA:

{S | S ∈ ∑ * и δ * (q 0 , S) ∈ F}

Строка S ′ не принимается DFA / NDFA (Q, ∑, δ, q 0 , F), если

δ * (q 0 , S ′) ∉ F

Язык L ′ не принят DFA / NDFA (дополнение к принятому языку L)

{S | S ∈ ∑ * и δ * (q 0 , S) ∉ F}

пример

Давайте рассмотрим DFA, показанный на рисунке 1.3. Из DFA, приемлемые строки могут быть получены.

Приемлемость строки по DFA

Строки, принятые вышеуказанным DFA: {0, 00, 11, 010, 101, ………..}

Строки, не принятые вышеуказанным DFA: {1, 011, 111, ……..}