In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined.

PropertyValue
dbpedia-owl:abstract
  • Ein nichtdeterministischer endlicher Automat ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
  • In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction. Both types of automata recognize only regular languages. Non-deterministic finite state machines are sometimes studied by the name subshifts of finite type. Non-deterministic finite state machines are generalized by probabilistic automata, which assign a probability to each state transition. Nondeterministic finite automata were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to deterministic finite automata.
  • Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible. En un AFND puede darse cualquiera de estos dos casos: Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2; Que existan transiciones del tipo δ, siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados. Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciónes vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.
  • Nella teoria del calcolo, un automa a stati finiti non deterministico (in inglese nondeterministic finite automaton, NFA) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione. Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.
  • 非決定性有限オートマトン（ひけっていせいゆうげん-、Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい、Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。
  • Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) - maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.
  • Na teoria da computação, uma máquina de estados finita não determinística ou autômato finito não-determinístico (NFA) é uma máquina de estados finitos onde para cada par estado e símbolo de entrada podem haver vários próximos estados possíveis.
  • 在计算理论中，非确定有限状态自动机或非确定有限自动机(NFA)是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机(DFA)，它的下一个可能状态是唯一确定的。尽管 DFA 和 NFA 有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定 NFA，都可以构造一个等价的 DFA，反之亦然: 通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为有限类型的子移位(subshift)。非确定有限状态自动机可推广为概率自动机，它为每个状态转移指派概率。 非确定有限自动机是 Michael O. Rabin 和 Dana Scott 在 1959 年介入的，他们证明了它与确定自动机的等价性。
dcterms:subject
rdf:type
rdfs:comment
  • Ein nichtdeterministischer endlicher Automat ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
  • Nella teoria del calcolo, un automa a stati finiti non deterministico (in inglese nondeterministic finite automaton, NFA) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione. Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.
  • 非決定性有限オートマトン（ひけっていせいゆうげん-、Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい、Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。
  • Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) - maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.
  • Na teoria da computação, uma máquina de estados finita não determinística ou autômato finito não-determinístico (NFA) é uma máquina de estados finitos onde para cada par estado e símbolo de entrada podem haver vários próximos estados possíveis.
  • 在计算理论中，非确定有限状态自动机或非确定有限自动机(NFA)是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机(DFA)，它的下一个可能状态是唯一确定的。尽管 DFA 和 NFA 有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定 NFA，都可以构造一个等价的 DFA，反之亦然: 通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为有限类型的子移位(subshift)。非确定有限状态自动机可推广为概率自动机，它为每个状态转移指派概率。 非确定有限自动机是 Michael O. Rabin 和 Dana Scott 在 1959 年介入的，他们证明了它与确定自动机的等价性。
  • In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined.
  • Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
rdfs:label
  • Nichtdeterministischer endlicher Automat
  • Nondeterministic finite-state machine
  • Autómata finito no determinista
  • Automa a stati finiti non deterministico
  • 非決定性有限オートマトン
  • Niedeterministyczny automat skończony
  • Máquina de estados finitos não determinística
  • 非确定有限状态自动机
owl:sameAs
foaf:page
is dbpedia-owl:knownFor of
is dbpedia-owl:wikiPageRedirects of
is dbpprop:knownFor of
is owl:sameAs of
is foaf:primaryTopic of