| rdfs:comment
| - Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) 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. (de)
- 非決定性有限オートマトン（ひけっていせいゆうげん-（）、英: Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい（）、英: Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。 (ja)
- 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ą relacji 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. (pl)
- Nella teoria del calcolo, un automa a stati finiti non deterministico (ASFND, 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. (it)
- 在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为（subshift）。非确定有限状态自动机可推广为，它为每个状态转移指派概率。 非确定有限自动机是和达纳·斯科特（Dana Scott）在1959年介入的，他们证明了它与确定自动机的等价性。 (zh)
- الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (NFA) في المعلوماتية النظرية هو ماكينة محدودة الحالات حيث قد يؤدي كل زوج مكون من رمز من رموز المدخلات وأحد الحالات إلى عدد من الحالات في الخطوة التالية، وهذا ما يميز هذا النموذج عن نموذج التشغيل الذاتي المحدود القطعي (DFA) حيث تكون الحالة المحتملة التالية حالة واحدة فقط. برغم أن لكل من النموذجين تعريف مختلف، يمكن إثبات أنهما متساويان في النظرية الشكلية حيث يمكن إنشاء DFA مكافئ لأي NFA والعكس صحيح، وهذا ما يسمى بإنشاء المجموعة المضاعفة. يتعرف كلا النموذجين على فقط. تدرس نماذج التشغيل المحدودة غير القطعية أحيانا باسم مساحة التنقل محدودة النوع. يعتبر نموذج التشغيل الاحتمالي الذي يعطي لكل نقلة من حالة إلى أخرى احتمالية نموذجا أعم من نموذج التشغيل المحدود غير القطعي.قدم ودانا سكوت نموذج التشغيل المحدود غير القطعي (ar)
- Un autòmat finit no determinista (abreujat AFND ) és un autòmat finit que, a diferència dels autòmats finits deterministes (AFD), té almenys un estat q ∈ Q , tal que per a un símbol a ∈ Σ de l'alfabet, hi ha més d'una transició δ ( q , a ) possible. En un AFND pot donar-se qualsevol d'aquests dos casos:
* Que hi hagi transicions del tipus δ ( q , a ) = q 1 i δ ( q , a ) = q 2 , sent q 1 ≠ q 2 ;
* Que hi hagi transicions del tipus δ ( q , ), sent q un estat no-final, o bé un estat final però amb transicions cap a altres estats. (ca)
- Στη θεωρία υπολογισμού, το μη ντετερμινιστικό πεπερασμένο αυτόματο (αγγλικά: nondeterministic finite-state automaton (NFA) ) είναι ένα που από μία κατάσταση, διαβάζοντας ένα σύμβολο εισόδου, μπορεί να μεταβεί σε μία ή και παραπάνω καταστάσεις, σε αντίθεση με το ντετερμινιστικό πεπερασμένο αυτόματο (DFA) που μπορεί να μεταβεί σε μία μόνο κατάσταση. Τα αυτόματα αυτά είναι πεπερασμένα, επειδή ο αριθμός των καταστάσεών τους είναι πεπερασμένος. Τα μη ντετερμιστικά πεπερασμένα αυτόματα εισήχθησαν το 1959 από τους και Ντέινα Σκοτ. (el)
- 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. Todo AFND puede ser convertido en un AFD equivalente. 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 δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados. (es)
- In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is uniquely determined by its source state and input symbol, and
* reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. (en)
- Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. (fr)
- 오토마타 이론에서, 어떤 유한 상태 기계가 결정적 유한 상태 기계(DFA)라는 것은 다음을 뜻한다.
* 현재 상태와 입력에 따라 다음 상태가 유일하게 결정된다.
* 상태가 바뀌려면 입력이 필요하다. 비결정적 유한 상태 기계(Nondeterministic finite automaton, NFA)는 이러한 제한을 따르지 않을 수도 있다. 모든 DFA는 NFA이기도 하다. NFA는 좁은 뜻으로는 DFA가 아닌 유한 상태 기계만을 가리키기도 하지만, 이 문서에서는 그렇게 하지 않는다. 을 사용하면 주어진 NFA와 동등한 DFA를 만들 수 있다. 즉, 주어진 NFA와 같은 언어를 인지하는 DFA를 만들 수 있다. DFA와 마찬가지로 NFA가 인지할 수 있는 언어는 정규 언어뿐이다. 미하엘 라빈과 데이나 스콧은 1959년에 비결정적 유한 상태 기계를 처음 도입했고 NFA와 DFA가 동등함을 보였다. NFA는 정규 표현식의 구현에 사용된다. 은 정규 표현식을 NFA로 바꾸어 효율적인 문자열 패턴 매칭을 가능케 하는 알고리즘이다. 반대로 은 NFA를 정규 표현식으로 바꾸어 준다. (이때 정규 표현식의 길이는 NFA의 크기에 따라 지수적으로 증가한다.) (ko)
- Na teoria da computação, uma máquina de estados finita não-determinística ou um autômato finito não-determinístico (AFND) é uma máquina de estados finita onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Isso o distingue do autômato finito determinístico (AFD), onde o próximo estado possível é univocamente determinado. Embora AFD e AFND possuam definições distintas, pode ser mostrado na teoria formal que eles são equivalentes e, deste modo, para qualquer AFND dado, pode-se construir um AFD equivalente e vice-versa: essa é a construção do conjunto das partes. Ambos os tipos de autômatos reconhecem apenas linguagens regulares. Máquinas de estados finitas não-determinísticas são às vezes estudadas com o nome de . (pt)
- Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:
* любой его переход единственным образом определяется по текущему состоянию и входному символу
* чтение входного символа требуется для каждого изменения состояния. В частности, любой ДКА является также НКА. Используя , любой НКА можно преобразовать в эквивалентный ДКА, то есть ДКА, распознающий тот же самый формальный язык. Подобно ДКА, НКА распознаёт только регулярные языки. (ru)
- Недетермінований автомат — абстрактний автомат, який при даному вхідному символі і внутрішньому стані може переходити в декілька різних внутрішніх станів. Формально, недетермінований автомат — це п'ятірка <X, Y, Q, Φ, Ψ>, така, що відображення Ψ: X × Q → Q не є однозначним. (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)