| http://dbpedia.org/ontology/abstract
|
Na teoria da computação, uma máquina de es … 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 . Máquinas de estados finitas não-determinísticas são generalizadas pelo autômato probabilístico, o qual atribui uma probabilidade para cada transição de estado, e por várias outras maneiras, tais como autômatos com pilha e AFNs com transições ε. Autômatos finitos não-determinísticos foram introduzidos em 1959 por Michael O. Rabin e Dana Scott, que também mostraram sua equivalência com autômatos finitos determinísticos.cia com autômatos finitos determinísticos.
, Ein nichtdeterministischer endlicher Autom … 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.egeben, welchen Übergang er zu wählen hat.
, Недетермінований автомат — абстрактний авт … Недетермінований автомат — абстрактний автомат, який при даному вхідному символі і внутрішньому стані може переходити в декілька різних внутрішніх станів. Формально, недетермінований автомат — це п'ятірка <X, Y, Q, Φ, Ψ>, така, що відображення Ψ: X × Q → Q не є однозначним. За аналогією з теорією детермінованих автоматів можна ввести поняття представлення (породження) множин для недетермінованих автоматів. Якщо два скінченних автомати, які представляють ту саму множину, вважати еквівалентними, то існує алгоритм, який дозволяє за кожним скінченним недетермінованим автоматом побудувати еквівалентний йому скінченний детермінований автомат. При цьому зрозуміло, що детермінований автомат має більшу кількість станів, ніж недетермінований автомат. Загалом для довільних автоматів це твердження не є правильним. Наприклад, клас множин, які породжуються недетермінованими автоматами зі стековою пам'яттю, ширше, ніж клас множин, які породжуються такими ж детермінованими автоматами.ються такими ж детермінованими автоматами.
, Στη θεωρία υπολογισμού, το μη ντετερμινιστ … Στη θεωρία υπολογισμού, το μη ντετερμινιστικό πεπερασμένο αυτόματο (αγγλικά: nondeterministic finite-state automaton (NFA) ) είναι ένα που από μία κατάσταση, διαβάζοντας ένα σύμβολο εισόδου, μπορεί να μεταβεί σε μία ή και παραπάνω καταστάσεις, σε αντίθεση με το ντετερμινιστικό πεπερασμένο αυτόματο (DFA) που μπορεί να μεταβεί σε μία μόνο κατάσταση. Τα αυτόματα αυτά είναι πεπερασμένα, επειδή ο αριθμός των καταστάσεών τους είναι πεπερασμένος. Τα μη ντετερμιστικά πεπερασμένα αυτόματα μπορούν να αναγνωρίσουν μόνο κανονικές γλώσσες, όπως και τα ντετερμινιστικά πεπερασμένα αυτόματα. Μάλιστα, για κάθε μη ντετερμινιστικό πεπερασμένο αυτόματο που αναγνωρίζει μια γλώσσα, υπάρχει ένα ισοδύναμο ντετερμινιστικό που αναγνωρίζει την ίδια γλώσσα. Τα μη ντετερμιστικά πεπερασμένα αυτόματα εισήχθησαν το 1959 από τους και Ντέινα Σκοτ.σήχθησαν το 1959 από τους και Ντέινα Σκοτ.
, In automata theory, a finite-state machine … 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. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton). NFAs have been generalized in multiple ways, e.g., , finite-state transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata.Besides the DFAs, other known special cases of NFAsare unambiguous finite automata (UFA)and self-verifying finite automata (SVFA).and self-verifying finite automata (SVFA).
, Недетерминированный конечный автомат (НКА, … Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:
* любой его переход единственным образом определяется по текущему состоянию и входному символу
* чтение входного символа требуется для каждого изменения состояния. В частности, любой ДКА является также НКА. Используя , любой НКА можно преобразовать в эквивалентный ДКА, то есть ДКА, распознающий тот же самый формальный язык. Подобно ДКА, НКА распознаёт только регулярные языки. НКА предложили в 1959 году Михаэль О. Рабин и Дана Скотт, которые показали его эквивалентность ДКА. НКА используется в реализации регулярных выражений — является алгоритмом для преобразования регулярного выражения в НКА, который может эффективно распознавать шаблон строк. Обратно, можно использовать для преобразования НКА в регулярное выражение, размер которого в общем случае экспоненциально зависит от размера автомата. НКА обобщён многими путями, например: , преобразователями с конечным числом состояний, автоматами с магазинной памятью, альтернирующими автоматами, ω-автоматами и вероятностными автоматами. Кроме ДКА известны другие специальные случаи НКА — (англ. unambiguous finite automata, UFA) и (англ. self-verifying finite automata, SVFA).гл. self-verifying finite automata, SVFA).
, الماكينة محدودة الحالات غير القطعية أو نمو … الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (NFA) في المعلوماتية النظرية هو ماكينة محدودة الحالات حيث قد يؤدي كل زوج مكون من رمز من رموز المدخلات وأحد الحالات إلى عدد من الحالات في الخطوة التالية، وهذا ما يميز هذا النموذج عن نموذج التشغيل الذاتي المحدود القطعي (DFA) حيث تكون الحالة المحتملة التالية حالة واحدة فقط. برغم أن لكل من النموذجين تعريف مختلف، يمكن إثبات أنهما متساويان في النظرية الشكلية حيث يمكن إنشاء DFA مكافئ لأي NFA والعكس صحيح، وهذا ما يسمى بإنشاء المجموعة المضاعفة. يتعرف كلا النموذجين على فقط. تدرس نماذج التشغيل المحدودة غير القطعية أحيانا باسم مساحة التنقل محدودة النوع. يعتبر نموذج التشغيل الاحتمالي الذي يعطي لكل نقلة من حالة إلى أخرى احتمالية نموذجا أعم من نموذج التشغيل المحدود غير القطعي.قدم ودانا سكوت نموذج التشغيل المحدود غير القطعي عام 1959، وهما من بينا أيضا مكافأته لنموذج التشغيل المحدود القطعي.يضا مكافأته لنموذج التشغيل المحدود القطعي.
, Un automate fini (on dit parfois, par une … 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. On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non. Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing. Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-dessus, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est : . L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle.Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final). Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaquelettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 : transition de l'automate de la figure 1 :
, 오토마타 이론에서, 어떤 유한 상태 기계가 결정적 유한 상태 기계(DFA)라 … 오토마타 이론에서, 어떤 유한 상태 기계가 결정적 유한 상태 기계(DFA)라는 것은 다음을 뜻한다.
* 현재 상태와 입력에 따라 다음 상태가 유일하게 결정된다.
* 상태가 바뀌려면 입력이 필요하다. 비결정적 유한 상태 기계(Nondeterministic finite automaton, NFA)는 이러한 제한을 따르지 않을 수도 있다. 모든 DFA는 NFA이기도 하다. NFA는 좁은 뜻으로는 DFA가 아닌 유한 상태 기계만을 가리키기도 하지만, 이 문서에서는 그렇게 하지 않는다. 을 사용하면 주어진 NFA와 동등한 DFA를 만들 수 있다. 즉, 주어진 NFA와 같은 언어를 인지하는 DFA를 만들 수 있다. DFA와 마찬가지로 NFA가 인지할 수 있는 언어는 정규 언어뿐이다. 미하엘 라빈과 데이나 스콧은 1959년에 비결정적 유한 상태 기계를 처음 도입했고 NFA와 DFA가 동등함을 보였다. NFA는 정규 표현식의 구현에 사용된다. 은 정규 표현식을 NFA로 바꾸어 효율적인 문자열 패턴 매칭을 가능케 하는 알고리즘이다. 반대로 은 NFA를 정규 표현식으로 바꾸어 준다. (이때 정규 표현식의 길이는 NFA의 크기에 따라 지수적으로 증가한다.) NFA를 더 일반화한 개념으로 , , 푸시다운 오토마타, , , 등이 있다. NFA의 특수한 예로는 DFA 말고도 (UFA)와 (SVFA) 등이 있다. NFA의 특수한 예로는 DFA 말고도 (UFA)와 (SVFA) 등이 있다.
, 非決定性有限オートマトン（ひけっていせいゆうげん-（）、英: Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい（）、英: Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。
, 在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号 … 在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为（subshift）。非确定有限状态自动机可推广为，它为每个状态转移指派概率。 非确定有限自动机是和达纳·斯科特（Dana Scott）在1959年介入的，他们证明了它与确定自动机的等价性。斯科特（Dana Scott）在1959年介入的，他们证明了它与确定自动机的等价性。
, Un autómata finito no determinista (abrevi … 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. Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones 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. estado sobre el mismo símbolo de entrada.
, Niedeterministyczny automat skończony (ang … 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.mówimy że automat akceptuje czytane słowo.
, Un autòmat finit no determinista (abreujat … 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. Quan es compleix el segon cas, es diu que l'autòmat és un autòmat finit no determinista amb transicions buides o transicions ε (abreujat AFND-ε ). Aquestes transicions permeten l'autòmat canviar d'estat sense processar cap símbol d'entrada.Considerem una modificació al model de l'autòmat finit per permetre cap, una o més transicions d'un estat sobre el mateix símbol d'entrada.un estat sobre el mateix símbol d'entrada.
, Nella teoria del calcolo, un automa a stat … 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.ipo di transizioni sono anche detti ε-NFA.
|
| rdfs:comment |
Na teoria da computação, uma máquina de es … 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 .cas são às vezes estudadas com o nome de .
, In automata theory, a finite-state machine … 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.hat is not a DFA, but not in this article.
, 非決定性有限オートマトン（ひけっていせいゆうげん-（）、英: Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい（）、英: Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。
, Ein nichtdeterministischer endlicher Autom … 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.egeben, welchen Übergang er zu wählen hat.
, Недетермінований автомат — абстрактний авт … Недетермінований автомат — абстрактний автомат, який при даному вхідному символі і внутрішньому стані може переходити в декілька різних внутрішніх станів. Формально, недетермінований автомат — це п'ятірка <X, Y, Q, Φ, Ψ>, така, що відображення Ψ: X × Q → Q не є однозначним.ідображення Ψ: X × Q → Q не є однозначним.
, 오토마타 이론에서, 어떤 유한 상태 기계가 결정적 유한 상태 기계(DFA)라 … 오토마타 이론에서, 어떤 유한 상태 기계가 결정적 유한 상태 기계(DFA)라는 것은 다음을 뜻한다.
* 현재 상태와 입력에 따라 다음 상태가 유일하게 결정된다.
* 상태가 바뀌려면 입력이 필요하다. 비결정적 유한 상태 기계(Nondeterministic finite automaton, NFA)는 이러한 제한을 따르지 않을 수도 있다. 모든 DFA는 NFA이기도 하다. NFA는 좁은 뜻으로는 DFA가 아닌 유한 상태 기계만을 가리키기도 하지만, 이 문서에서는 그렇게 하지 않는다. 을 사용하면 주어진 NFA와 동등한 DFA를 만들 수 있다. 즉, 주어진 NFA와 같은 언어를 인지하는 DFA를 만들 수 있다. DFA와 마찬가지로 NFA가 인지할 수 있는 언어는 정규 언어뿐이다. 미하엘 라빈과 데이나 스콧은 1959년에 비결정적 유한 상태 기계를 처음 도입했고 NFA와 DFA가 동등함을 보였다. NFA는 정규 표현식의 구현에 사용된다. 은 정규 표현식을 NFA로 바꾸어 효율적인 문자열 패턴 매칭을 가능케 하는 알고리즘이다. 반대로 은 NFA를 정규 표현식으로 바꾸어 준다. (이때 정규 표현식의 길이는 NFA의 크기에 따라 지수적으로 증가한다.). (이때 정규 표현식의 길이는 NFA의 크기에 따라 지수적으로 증가한다.)
, Στη θεωρία υπολογισμού, το μη ντετερμινιστ … Στη θεωρία υπολογισμού, το μη ντετερμινιστικό πεπερασμένο αυτόματο (αγγλικά: nondeterministic finite-state automaton (NFA) ) είναι ένα που από μία κατάσταση, διαβάζοντας ένα σύμβολο εισόδου, μπορεί να μεταβεί σε μία ή και παραπάνω καταστάσεις, σε αντίθεση με το ντετερμινιστικό πεπερασμένο αυτόματο (DFA) που μπορεί να μεταβεί σε μία μόνο κατάσταση. Τα αυτόματα αυτά είναι πεπερασμένα, επειδή ο αριθμός των καταστάσεών τους είναι πεπερασμένος. Τα μη ντετερμιστικά πεπερασμένα αυτόματα εισήχθησαν το 1959 από τους και Ντέινα Σκοτ.σήχθησαν το 1959 από τους και Ντέινα Σκοτ.
, Nella teoria del calcolo, un automa a stat … 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.ipo di transizioni sono anche detti ε-NFA.
, Niedeterministyczny automat skończony (ang … 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.mówimy że automat akceptuje czytane słowo.
, Un autòmat finit no determinista (abreujat … 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. però amb transicions cap a altres estats.
, 在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号 … 在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为（subshift）。非确定有限状态自动机可推广为，它为每个状态转移指派概率。 非确定有限自动机是和达纳·斯科特（Dana Scott）在1959年介入的，他们证明了它与确定自动机的等价性。斯科特（Dana Scott）在1959年介入的，他们证明了它与确定自动机的等价性。
, Un autómata finito no determinista (abrevi … 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.pero con transiciones hacia otros estados.
, الماكينة محدودة الحالات غير القطعية أو نمو … الماكينة محدودة الحالات غير القطعية أو نموذج التشغيل الذاتي المحدود غير القطعي (NFA) في المعلوماتية النظرية هو ماكينة محدودة الحالات حيث قد يؤدي كل زوج مكون من رمز من رموز المدخلات وأحد الحالات إلى عدد من الحالات في الخطوة التالية، وهذا ما يميز هذا النموذج عن نموذج التشغيل الذاتي المحدود القطعي (DFA) حيث تكون الحالة المحتملة التالية حالة واحدة فقط. برغم أن لكل من النموذجين تعريف مختلف، يمكن إثبات أنهما متساويان في النظرية الشكلية حيث يمكن إنشاء DFA مكافئ لأي NFA والعكس صحيح، وهذا ما يسمى بإنشاء المجموعة المضاعفة. يتعرف كلا النموذجين على فقط. تدرس نماذج التشغيل المحدودة غير القطعية أحيانا باسم مساحة التنقل محدودة النوع. يعتبر نموذج التشغيل الاحتمالي الذي يعطي لكل نقلة من حالة إلى أخرى احتمالية نموذجا أعم من نموذج التشغيل المحدود غير القطعي.قدم ودانا سكوت نموذج التشغيل المحدود غير القطعي انا سكوت نموذج التشغيل المحدود غير القطعي
, Un automate fini (on dit parfois, par une … 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.ans la recherche des motifs dans un texte.
, Недетерминированный конечный автомат (НКА, … Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:
* любой его переход единственным образом определяется по текущему состоянию и входному символу
* чтение входного символа требуется для каждого изменения состояния. В частности, любой ДКА является также НКА. Используя , любой НКА можно преобразовать в эквивалентный ДКА, то есть ДКА, распознающий тот же самый формальный язык. Подобно ДКА, НКА распознаёт только регулярные языки.А, НКА распознаёт только регулярные языки.
|
