Почему NFA называется недетерминированным?

14

Я имею в виду этот [забавный] вопрос. Почему недетерминированный конечный автомат называется недетерминированным, в то время как мы определяем переходы для входных данных. Что ж, несмотря на то, что существуют множественные и эпсилон- переходы, они определены, что означает, что машина является детерминированной для этих переходов. Что означает, что это детерминировано.

finite-automata nondeterminism Madhusoodan P
источник

12

Недетерминированный, используемый в теоретической информатике, отличается от случайного.

adrianN

10

Это выбор между переходами, который является недетерминированным.

reinierpost

Что такое NFA? (Для непросветленных среди нас)

DarcyThomas

@DarcyThomas, первое мое знакомство было swtch.com/~rsc/regexp/regexp1.html . Это хорошая статья - цель этой статьи не в том, чтобы представить NFA, но она хорошо справляется с обсуждением регулярных выражений.

Wildcard

1

@Trilarion cs.stackexchange.com/questions/5008/…

adrianN

22

«Детерминистический» означает «если вы поместите систему в одну и ту же ситуацию дважды, она гарантированно сделает один и тот же выбор оба раза».

«Недетерминированный» означает «недетерминированный» или, другими словами, «если вы дважды ставите систему в одну и ту же ситуацию, она может или не может сделать один и тот же выбор оба раза».

Недетерминированный конечный автомат (NFA) может иметь несколько переходов из состояния. Это означает, что есть несколько вариантов того, что он может сделать в этой ситуации. Не обязательно всегда выбирать один и тот же; на одном входе он может выбрать первый переход, а на другом - тот же переход.

Здесь вы можете думать о «ситуации» как о «состоянии, в котором находится NFA, вместе с тем, какой символ читается после ввода». Даже если оба они одинаковы, NFA может иметь несколько совпадающих переходов, которые можно вывести из этого состояния, и он может произвольно выбирать, какой из них выбрать. Напротив, у DFA есть только один соответствующий переход, который может быть выполнен в этой ситуации, поэтому у него нет выбора - он всегда будет следовать одному и тому же переходу, когда он находится в этой ситуации.

DW
источник

«Он может выбрать произвольно, какой взять». Так что это в основном имеет вероятностный характер?

Триларион,

@ Триларион, нет, это зависит от того, приведет ли это к принятию государства. На самом деле вероятностный FA является обобщением для NFA.

rus9384

«Недетерминированный» означает «недетерминированный», или, другими словами, «если вы ставите систему в одну и ту же ситуацию дважды, она может или не может сделать один и тот же выбор оба раза». под этим вы подразумеваете, что машина может принимать и отклонять одну и ту же строку в двух разных случаях.

Madhusoodan P

3

@MadhusoodanP Ваша интуиция верна из того, что было здесь написано, и это приводит нас к тому, чего не хватает в этом ответе: при анализе NFA мы всегда учитываем все возможные пути выполнения. Пока любой путь в этой машине ведет к принимающему состоянию, мы считаем входные данные принятыми. Так что дело вовсе не в вероятности, а просто в том, может ли быть достигнуто принимающее состояние или нет. Эта интуиция становится яснее, когда мы думаем о том, как NFA сводятся к DFA: мы должны смоделировать все возможные исполнения NFA, что приводит к экспоненциальному взрыву в конструкции.

ComicSansMS

3

Один из способов визуализации - предположить, что при выборе нескольких переходов NFA принимает все переходы. Вы создаете древовидную структуру всех состояний, достигнутых входной строкой, и, если любая из ветвей заканчивается в состоянии принятия, строка принимается. Другими словами, в DFA вы спрашиваете: « Достигнуто ли состояние моего ввода в состоянии принятия?», В то время как в NFA вы спрашиваете «может ли какое-либо состояние, которое может быть достигнуто моим входом, в состоянии принятия?

Харрисон Пэйн

8

Возьмите этот автомат, например, это NFA, и он принимает строку . Чтобы быть более педантичным, он принимает строки, заканчивающиеся на . $0110$ $10$

Чтобы увидеть, что нам просто нужно проверить, достигает ли он состояния принятия.

\begin{aligned} Q_{0} & \to 1 \\ Q_{0} & \to 0 \\ Q_{1} & \to 1 \\ Q_{2} & \to 0 \end{aligned}

$\begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{align*}$

Теперь у красной линии была другая возможность, то есть, читая вторую я мог остаться в и затем остаться в $1$ $q_0$ при чтении последней . Автоматы не имеют памяти, поэтому нет никакого способа «сохранить» состояние и проверить позже, заканчивается ли моя строка на , похоже, что этот NFA делает предположение, заканчивается ли строка на прежде чем перейти в приемлемое состояние. Здесь недетерминизм делает много выборов и всегда делает правильные. $q_0$ $0$ $10$ $10$

Построить NFA легче, чем построить DFA, хорошо то, что оба они эквивалентны .

Aristu
источник

Да, я знаю теоретическую часть NFA. Но то, что я спрашивал, было то, что несмотря на то, что для одного входного символа было несколько переходов, машина детерминирована в отношении того, что все состояния могут достигать (например, путем создания потоков). Следовательно, это буквально DFA. [Или вы думаете, что я неверно истолковываю значение детерминизма ]

Madhusoodan P

1

Пример может быть улучшен с помощью немного более сложного NFA, поскольку DFA для той же цели будет использовать то же число состояний, что и ваш NFA, и не будет особенно сложным. Напротив, сопоставление с более сложным регулярным выражением может потребовать сложного и запутанного DFA, но в NFA может быть тривиальным.

суперкат

ε

$\varepsilon$

1

@Aristu Если вы реализуете NFA на своем любимом языке программирования, потоки - это ужасный выбор. Скорее, вы должны просто отслеживать набор состояний, в которых автомат «может находиться» после считывания каждого символа ввода. Полученный код будет почти таким же быстрым, как и реализация DFA.

Дэвид Ричерби

1

ϵ

$\epsilon$

5

Функция перехода NFA определяет разрешенные переходы в любой момент времени. Может быть более одного варианта, и NFA выбирает переход недетерминированно с целью в конечном итоге достичь принимающего состояния.

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

Юваль Фильмус
источник

Можете ли вы выделить этот «недетерминированный переход». А также, пожалуйста, просмотрите мой ответ

Madhusoodan P

Я думаю, что оба наших ответа не очень хороши, хотя ваша интуиция здорова.

Юваль

3

Начните с конечного автомата. У него есть состояния и состояния принятия и переходы.

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

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

Это недетерминированный. После того, как вы решите всю проблему, он выбирает путь по графику, а не по мере чтения ввода.

Теперь мы формализуем это иначе, чем этот мысленный эксперимент, но это дает вам мотивацию, почему он получил это имя.

Это объясняет, как он получил имя в первую очередь. Да, вы можете смоделировать NDFA полностью детерминированным способом, но имена являются липкими . После того, как вы назвали что-то, Боб, вам придется переименовать его в другое, поскольку никто не знает, о чем вы говорите, когда называете это Алисой.

Yakk
источник

да! Я согласен с вашим объяснением о NFA. Но мой вопрос о том, почему он недетерминирован, хотя набор состояний определен для одного входа

Madhusoodan P

@MadhusoodanP Это называется недетерминированным из-за того, как оно было изобретено / задумано. И имена являются липкими, даже после того, как мы определили многопользовательские полностью детерминированные способы его моделирования.

Якк

1

Из википедии лучший способ подумать об этом - начать с детерминированных конечных автоматов (DFA). Для DFA каждый переход однозначно определяется текущим состоянием и обрабатываемым символом ввода. Недетерминированные конечные автоматы (NFA) - это просто то, что вы получаете, когда вы ослабляете это правило детерминизма, чтобы позволить переходам не быть однозначно определенными. Это то, что вы получаете, когда удаляете правило детерминированного из DFA.

Корт Аммон
источник

Это немного сложнее, поскольку недетерминизм также является особым условием принятия.

Ювал

1

NFA и DFA оба используются (среди прочего) для распознавания определенных строк.

Недетерминированный конечный автомат работает так, как будто он влиял на его решения - он может «выбирать» следовать по пути или нет.

На изображении выше, когда мы имеем дело со строкой «00111», обратите внимание, что при обнаружении первой «1» есть два возможных способа следовать. Можно остаться на «р» или перейти к «д». Если бы автоматы должны были перейти к «q», он не принял бы строку (поскольку из «q» нет ребер). Но строка может быть принята этими автоматами, перейдя к «q» только с последней 1, оставаясь при этом «p» для всего остального (и это то, что происходит).

NFA заставляет это выглядеть так, будто автоматы «знали», что впереди, и выбирают соответственно.

Конечно нет. DFA и NFA эквивалентны по мощности (вы можете уменьшить NFA до DFA и сделать DFA (возможно) более простым с использованием NFA), но NFA полезен, потому что он позволяет определять те же языки, что и DFA, сохраняя при этом графики короче и читабельнее.

Там нет ничего случайного. Недетерминированная часть подчеркивает тот факт, что есть некоторый «выбор», но правда состоит в том, что автоматы не принимают никаких решений.

MatthewRock
источник

0

Ну, вот сочетание некоторого содержания из книги [Введение в формальные языки и автоматы Питера Линца 4E] и моего понимания.

Рассмотрим игровую программу, в которой машина должна принять решение для следующего хода [например, крестики-нолики]. Поскольку возможны несколько ходов, мы детерминистически выбираем каждый ход, оцениваем ход и выбираем лучший. Несмотря на то, что процесс отбора был детерминированным и было много возможных ходов, последний сделанный ход был единичным и был выбран как лучший ход, скрывая все проверенные вычисления ходов от оппонента. [Здесь мы предполагаем, что процесс оценки каждого возможного хода был скрыт от оппонента].

Следовательно, был сделан только один выбор, и у противника создается иллюзия, что ход был недетерминированным.

Что ж, если вы еще не уверены, спросив, что лучшим ходом был продукт некоторых детерминированных вычислений, то вы должны рассмотреть машину, которая совершает совершенно случайные движения (может быть, машина проигрывает, но это NFA).

Madhusoodan P
источник

1

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

reinierpost

@reinierpost именно то, что я хотел сказать

Madhusoodan P

Более интересным примером может быть игра с движущимися частями с ограниченной информацией (например, стиль «полицейские и грабители»). Один игрок перемещает грабителя вокруг лабиринта, в то время как другой игрок перемещает полицейских. В любое время, когда полицейский может видеть грабителя, состояние грабителя будет его местонахождением, но на любом ходу, когда ни один из копов не увидит грабителя, грабитель может перейти к любым клеткам, которые смежны с его положением, и что копы могут не вижу в этот момент.

суперкат

@supercat Хороший, но переход сделан всегда одним состоянием, и если вы скрываете вычисление лучшего хода, это кажется недетерминированным

Madhusoodan P

Почему NFA называется недетерминированным?

Ответы: