Deterministic finite automaton (original) (raw)
Un autòmat finit determinista (abreujat AFD ) és un autòmat finit que a més és un sistema determinista, és a dir, per a cada estat en què es trobi l'autòmat, i amb qualsevol símbol de l'alfabet llegit, existeix sempre pel cap alt una transició possible des d'aquest estat i amb aquest símbol.
| Property | Value |
|---|---|
| dbo:abstract | Un autòmat finit determinista (abreujat AFD ) és un autòmat finit que a més és un sistema determinista, és a dir, per a cada estat en què es trobi l'autòmat, i amb qualsevol símbol de l'alfabet llegit, existeix sempre pel cap alt una transició possible des d'aquest estat i amb aquest símbol. (ca) في نظرية الاتمتة ونظرية التشغيل الذاتي, فرع من فروع علم الحاسوب, الاتمتة المحدودة القطعية Deterministic Finite Automaton أو DFA اختصاراً أي الآلة المحدودة المدخلات وقطعية أو معروفة المخرجات الآلة ذاتية التشغيل (محددة), هي آلة تقوم بقبول أو رفض الحروف أو الرموز وتنتج عملية حسابية معينة عند عملها أو عند ادخال الحروف أو الرموز عليها, قدم ابسط صورها العالمان في عام 1943. الصورة على اليمين هو تمثيل لـ آلة محدودة قطعية باستخدام النماذج الرياضية. في هذه الآلة هناك ثلاث حالات : S0, S1 و S2 (حيث كل دائرة تدل على حالة). هذه الآلة تقبل عدد محدود من ال 0 والـ 1 كمدخلات. في كل حالة من الثلاث حالات هناك سهم انتقال من حاله إلى أخرى. في حالة قرائة رمز أو حرف معين 0 و 1 في هذه الحالة الآلة تنتقل من حالة إلى أخرى بشكل قطعي ومحدد. الـ DFA معرفة كـ النماذج الرياضية, لكن بسبب طبيعتها القطعية, هي مطبقة في البرمجيات والـعتاد الحاسوب لحل العديد من المشاكل المحددة. على سبيل المثال : نموذج رياضي يمثل DFA يطبق كبرمجية تقوم بتقرير ما ان كان أحد المستخدمين على الشبكة ام لا أو تدقيق بريده الإلكتروني على سبيل المثال. (ar) Το ντετερμινιστικό πεπερασμένο αυτόματο (deterministic finite state automaton ή DFA) είναι ένα , ένας εξιδανικευμένος νοητός υπολογιστής αποτελούμενος από έναν πεπερασμένο αριθμό καταστάσεων και μια συνάρτηση μετάβασης, μέσω της οποίας καθορίζονται οι μεταβάσεις από κατάσταση σε κατάσταση, ανάλογα με την είσοδο που δέχεται το αυτόματο. Η έξοδος του αυτόματου θα είναι είτε αποδοχή είτε απόρριψη της εισόδου. Επειδή οι καταστάσεις του αυτόματου είναι πεπερασμένου πλήθους και επειδή μέσω της συνάρτησης μετάβασης το αυτόματο μεταβαίνει σε μία μόνο κατάσταση, δηλαδή δεν υπάρχουν πάνω από μία επιλογές, το συγκεκριμένο υπολογιστικό μοντέλο είναι πεπερασμένο και ντετερμινιστικό. Τα ντετερμινιστικά πεπερασμένα αυτόματα αποτελούν μια κατηγορία των . Αναγνωρίζουν μόνο κανονικές γλώσσες. (el) Ein deterministischer endlicher Automat (DEA; englisch deterministic finite state machine oder deterministic finite automaton, DFA) ist in der theoretischen Informatik ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Von jedem (Final-)Zustand muss für jedes Zeichen des Eingabealphabets ein Übergang in einen Folgezustand existieren. Er unterscheidet sich darin von nichtdeterministischen endlichen Automaten, deren Zustandswechsel sich nicht immer deterministisch ereignen müssen. (de) In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943. The figure illustrates a deterministic finite automaton using a state diagram. In this example automaton, there are three states: S0, S1, and S2 (denoted graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state for both 0 and 1. Upon reading a symbol, a DFA jumps deterministically from one state to another by following the transition arrow. For example, if the automaton is currently in state S0 and the current input symbol is 1, then it deterministically jumps to state S1. A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful. A DFA is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving various specific problems such as lexical analysis and pattern matching. For example, a DFA can model software that decides whether or not online user input such as email addresses are syntactically valid. DFAs have been generalized to nondeterministic finite automata (NFA) which may have several arrows of the same label starting from a state. Using the powerset construction method, every NFA can be translated to a DFA that recognizes the same language. DFAs, and NFAs as well, recognize exactly the set of regular languages. (en) Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo. (es) Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné. Les automates finis déterministes ont plusieurs aspects avantageux : simplicité de leur définition, facilité de manipulation, aisance de la programmation informatique, élégance des propriétés mathématiques. Leur inconvénient majeur est la taille, mesurée en nombre d'états, qui peut dans certains cas être exponentielle par rapport à leur contre-part non déterministe. Les deux classes d'automates finis, les automates finis déterministes et non déterministes, ont la même puissance d'expression : elles reconnaissent la même famille de langages, à savoir les langages rationnels, appelés aussi langages réguliers ou langages reconnaissables. (fr) 계산이론의 한 분야인 이론 전산학에서 결정적 유한 오토마타(Deterministic finite automaton, DFA)는 각각의 입력 문자열 안의 각 심볼에 대하여 유일한 상태변화를 취하는 유한 상태 기계이다. 이 용어에서 결정적이란 계산의 유일함을 뜻한다. (ko) 決定性有限オートマトン（けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。 (ja) Nella teoria del calcolo, un automa a stati finiti deterministico (ASFD) o deterministic finite automaton (DFA) è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso c'è una ed una sola transizione allo stato successivo. (it) Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna 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 zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana. Deterministyczny automat skończony, podobnie jak inne automaty skończone może być reprezentowany za pomocą tabeli przejść pomiędzy stanami lub diagramu stanów. (pl) Na Teoria dos autômatos, um sub-tópico da Ciência da computação teórica, um autômato finito determinístico — também chamado máquina de estados finita determinística (AFD) — é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para cada cadeia de entrada. "Determinística" refere-se à unicidade do processamento.O primeiro conceito similar ao de autômatos finitos foi apresentado por McCulloch e Pitts em 1943. Modelo esse que foi produzido na busca por estruturas mais simples para a reprodução de máquinas de estado finitas. A figura à direita representa um autômato finito determinístico através de um Diagrama de transição de estados. Nesse autômato há três estados: S0, S1 e S2 (representados graficamente por círculos). A entrada é constituída por uma sequência finita de caracteres 1s e 0s. Para cada estado da máquina, existe um arco de transição levando a um outro estado para ambos caracteres 0 e 1. Isso significa que, em um dado estado, após a leitura de cada símbolo a máquina determinística transita para um único estado referente à aresta associada ao símbolo.Por exemplo, esteja o autômato atualmente no estado S0 e o símbolo de entrada para aquela instância um '1', então ele salta deterministicamente para o estado S1.Todo AFD possui um estado inicial (denotado graficamente por uma seta de origem anônima) onde a sua computação começa e um conjunto de estados de aceitação (denotados graficamente por um círculo de borda dupla) o qual indica a aceitação da cadeia de entrada. Um Autômato finito determinístico é normalmente definido como um conceito matemático abstrato, mas devido à seu fator determinístico, ele pode ser implementado através de Hardware e Software para resolver diversos problemas específicos. Por instância, AFDs são utilizados para modelar softwares que validam entradas de usuário tal como o seu e-mail em um servidor de correio eletrônico. AFDs reconhecem exatamente o conjunto de Linguagens Regulares que são, dentre outras coisas, úteis para a realização de Análise léxica e reconhecimento de padrões.Uma AFD pode ser construído a partir de um Autômato finito não determinístico através de uma Construção do conjunto das partes. (pt) Детерминированный конечный автомат (ДКА, DFA, англ. deterministic finite automaton, DFSA, англ. deterministic finite-state automaton, DFSM англ. deterministic finite-state machine), известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году. Рисунок иллюстрирует детерминированный конечный автомат с помощью диаграммы состояний. В этом примере имеется три состояния — S0, S1 и S2 (отражены на рисунке окружностями). Автомат на вход принимает конечную последовательность нулей и единиц. Для каждого состояния существует стрелка перехода, ведущая из состояния в другое состояние как для 0, так и для 1. После чтения символа, ДКА детерминированно переходит из одного состояния в другое, следуя по стрелке перехода. Например, если автомат находится в состоянии S0, а входным символом является 1, то автомат детерминированно переходит в состояние S1. ДКА имеет начальное состояние (графически показывается стрелкой «из ниоткуда»), откуда начинается вычисление, и множество конечных состояний (обозначаемых графически в виде двойной окружности), которые определяют, успешно ли закончились вычисления. ДКА определяется как абстрактная математическая концепция, но часто реализуется в аппаратном и программном обеспечении для решения специфичных задач. Например, ДКА может моделировать программы, которые решают допустим ли введённый пользователем email адрес. ДКА распознаёт в точности множество регулярных языков, которые, среди прочего, полезны для лексического анализа и сопоставления с образцом. ДКА могут быть построены из недетерминированного конечного автомата (НКА, англ. nondeterministic finite automata, NFAs) с помощью . (ru) В теорії алгоритмів і теорії автоматів, детермінований скінченний автомат (ДСА) — скінченний автомат, який приймає скінченний рядок символів. Для кожного стану існує стрілка переходу в наступний стан для кожного символу. Після зчитування символу ДСА перестрибує детерміновано з одного стану в інший за відповідною стрілкою. Детермінованість означає наявність лише одного результату (тобто переходу в наступний стан для кожного символу (S0 -> Si) або повернення в той самий стан (S0 -> S0)). ДСА має початковий стан (позначений графічно стрілкою нізвідки), звідки починаються обчислення, і набір допустимих станів (позначених графічно двійними колами), які допомагають визначити успішність обчислень. ДСА саме розпізнає набір регулярних мов, що є, між іншим, корисним для проведення лексичного аналізу і зіставляння зі взірцем.ДСА можна використати або в режимі приймача для перевірки належності вхідного рядка до мови, або в режимі генерації для створення списку всіх рядків у мові. ДСА визначається як абстрактна математична концепція, але через свою детермінованість він може бути виконаним на апаратному або програмному рівні для розв'язання різних особливих задач. Наприклад, програмний автомат, який визначає чи є введений рядок правильним телефонним номером або електронною адресою.Іншим прикладом на апаратному рівні є мікросхема, що керує автоматичними дверима, використовуючи вхідні дані від сенсорів руху або кнопок для визначення моменту, коли треба виконувати переходи між станами. (uk) 在计算理论中，确定有限状态自动机或确定有限自动机（英語：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/DFA_example_multiplies_of_3.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.researchgate.net/publication/230876408%7Cdoi= http://www.pearsonhighered.com/educator/product/Introduction-to-Automata-Theory-Languages-and-Computation/9780201441246.page https://archive.org/details/introductiontoth00sips |
| dbo:wikiPageID | 653404 (xsd:integer) |
| dbo:wikiPageLength | 29103 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113486814 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Powerset_construction dbr:Nondeterministic_finite_automaton dbr:Degeneracy_(graph_theory) dbr:Regular_expression dbr:Currying dbr:Deterministic_acyclic_finite_state_automaton dbr:Lexical_analysis dbr:Weighted_automaton dbr:Online_algorithm dbr:Quantum_finite_automaton dbr:Function_(mathematics) dbr:Function_composition dbr:Glossary_of_graph_theory dbr:Monoid dbr:Erdős–Rényi_model dbr:Alphabet_(computer_science) dbr:State_transition_table dbr:Partial_function dbr:State_(computer_science) dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:Transition_monoid dbr:Trie dbr:Tuple dbr:Walter_Pitts dbr:Drug-facilitated_sexual_assault dbr:Local_language_(formal_language) dbr:Semiautomaton dbr:DFA_minimization dbr:Dyck_language dbc:Finite_automata dbr:Breadth-first_search dbr:Directed_graph dbr:Formal_language dbr:Strongly_connected_component dbr:Regular_language dbr:State_diagram dbr:State_complexity dbr:Transition_system dbr:Automata_theory dbr:Marijn_Heule dbr:Boolean_satisfiability_problem dbr:Evolutionary_algorithms dbr:Kleene_closure dbr:Separating_words_problem dbr:Sequence dbr:Set_(mathematics) dbr:Kleene_star dbr:Monadic_second-order_logic dbr:Pattern_matching dbr:Turing_machine dbr:Vertex_(graph_theory) dbr:Nondeterministic_finite_automata dbr:Finite-state_machine dbr:Two-way_finite_automaton dbr:Warren_McCulloch dbr:State_transition_system dbr:PSPACE_complete dbr:Addison_Wesley dbr:N-tuple dbr:Closed_under dbr:File:DFAexample.svg dbr:File:DFA_example_multiplies_of_3.svg dbr:File:Intersection1.png |
| dbp:wikiPageUsesTemplate | dbt:Center dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Columns-list dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Rp dbt:Short_description dbt:Use_dmy_dates dbt:Redirect-synonym dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Finite_automata |
| rdf:type | yago:WikicatConceptualModels yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | Un autòmat finit determinista (abreujat AFD ) és un autòmat finit que a més és un sistema determinista, és a dir, per a cada estat en què es trobi l'autòmat, i amb qualsevol símbol de l'alfabet llegit, existeix sempre pel cap alt una transició possible des d'aquest estat i amb aquest símbol. (ca) Ein deterministischer endlicher Automat (DEA; englisch deterministic finite state machine oder deterministic finite automaton, DFA) ist in der theoretischen Informatik ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Von jedem (Final-)Zustand muss für jedes Zeichen des Eingabealphabets ein Übergang in einen Folgezustand existieren. Er unterscheidet sich darin von nichtdeterministischen endlichen Automaten, deren Zustandswechsel sich nicht immer deterministisch ereignen müssen. (de) Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo. (es) 계산이론의 한 분야인 이론 전산학에서 결정적 유한 오토마타(Deterministic finite automaton, DFA)는 각각의 입력 문자열 안의 각 심볼에 대하여 유일한 상태변화를 취하는 유한 상태 기계이다. 이 용어에서 결정적이란 계산의 유일함을 뜻한다. (ko) 決定性有限オートマトン（けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。 (ja) Nella teoria del calcolo, un automa a stati finiti deterministico (ASFD) o deterministic finite automaton (DFA) è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso c'è una ed una sola transizione allo stato successivo. (it) 在计算理论中，确定有限状态自动机或确定有限自动机（英語：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。 (zh) في نظرية الاتمتة ونظرية التشغيل الذاتي, فرع من فروع علم الحاسوب, الاتمتة المحدودة القطعية Deterministic Finite Automaton أو DFA اختصاراً أي الآلة المحدودة المدخلات وقطعية أو معروفة المخرجات الآلة ذاتية التشغيل (محددة), هي آلة تقوم بقبول أو رفض الحروف أو الرموز وتنتج عملية حسابية معينة عند عملها أو عند ادخال الحروف أو الرموز عليها, قدم ابسط صورها العالمان في عام 1943. (ar) Το ντετερμινιστικό πεπερασμένο αυτόματο (deterministic finite state automaton ή DFA) είναι ένα , ένας εξιδανικευμένος νοητός υπολογιστής αποτελούμενος από έναν πεπερασμένο αριθμό καταστάσεων και μια συνάρτηση μετάβασης, μέσω της οποίας καθορίζονται οι μεταβάσεις από κατάσταση σε κατάσταση, ανάλογα με την είσοδο που δέχεται το αυτόματο. Η έξοδος του αυτόματου θα είναι είτε αποδοχή είτε απόρριψη της εισόδου. Τα ντετερμινιστικά πεπερασμένα αυτόματα αποτελούν μια κατηγορία των . Αναγνωρίζουν μόνο κανονικές γλώσσες. (el) In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943. (en) Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné. (fr) Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna 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 zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana. (pl) Na Teoria dos autômatos, um sub-tópico da Ciência da computação teórica, um autômato finito determinístico — também chamado máquina de estados finita determinística (AFD) — é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para cada cadeia de entrada. "Determinística" refere-se à unicidade do processamento.O primeiro conceito similar ao de autômatos finitos foi apresentado por McCulloch e Pitts em 1943. Modelo esse que foi produzido na busca por estruturas mais simples para a reprodução de máquinas de estado finitas. (pt) Детерминированный конечный автомат (ДКА, DFA, англ. deterministic finite automaton, DFSA, англ. deterministic finite-state automaton, DFSM англ. deterministic finite-state machine), известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году. (ru) В теорії алгоритмів і теорії автоматів, детермінований скінченний автомат (ДСА) — скінченний автомат, який приймає скінченний рядок символів. Для кожного стану існує стрілка переходу в наступний стан для кожного символу. Після зчитування символу ДСА перестрибує детерміновано з одного стану в інший за відповідною стрілкою. Детермінованість означає наявність лише одного результату (тобто переходу в наступний стан для кожного символу (S0 -> Si) або повернення в той самий стан (S0 -> S0)). ДСА має початковий стан (позначений графічно стрілкою нізвідки), звідки починаються обчислення, і набір допустимих станів (позначених графічно двійними колами), які допомагають визначити успішність обчислень. (uk) |
| rdfs:label | أتمتة محدودة قطعية (ar) Autòmat finit determinista (ca) Deterministischer endlicher Automat (de) Ντετερμινιστικό πεπερασμένο αυτόματο (el) Autómata finito determinista (es) Deterministic finite automaton (en) Automate fini déterministe (fr) Automa a stati finiti deterministico (it) 決定性有限オートマトン (ja) 결정적 유한 상태 기계 (ko) Deterministyczny automat skończony (pl) Autômato finito determinístico (pt) Детерминированный конечный автомат (ru) Детермінований скінченний автомат (uk) 确定有限状态自动机 (zh) |
| owl:sameAs | freebase:Deterministic finite automaton yago-res:Deterministic finite automaton wikidata:Deterministic finite automaton dbpedia-ar:Deterministic finite automaton http://bs.dbpedia.org/resource/Deterministički_konačni_automat dbpedia-ca:Deterministic finite automaton dbpedia-de:Deterministic finite automaton dbpedia-el:Deterministic finite automaton dbpedia-es:Deterministic finite automaton dbpedia-fa:Deterministic finite automaton dbpedia-fr:Deterministic finite automaton dbpedia-he:Deterministic finite automaton dbpedia-hr:Deterministic finite automaton dbpedia-hu:Deterministic finite automaton dbpedia-it:Deterministic finite automaton dbpedia-ja:Deterministic finite automaton dbpedia-ko:Deterministic finite automaton http://lv.dbpedia.org/resource/Galīgs_determinēts_automāts dbpedia-no:Deterministic finite automaton dbpedia-pl:Deterministic finite automaton dbpedia-pt:Deterministic finite automaton dbpedia-ru:Deterministic finite automaton dbpedia-sh:Deterministic finite automaton dbpedia-sr:Deterministic finite automaton dbpedia-tr:Deterministic finite automaton dbpedia-uk:Deterministic finite automaton dbpedia-zh:Deterministic finite automaton https://global.dbpedia.org/id/4zfPT |
| prov:wasDerivedFrom | wikipedia-en:Deterministic_finite_automaton?oldid=1113486814&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DFAexample.svg wiki-commons:Special:FilePath/DFA_example_multiplies_of_3.svg wiki-commons:Special:FilePath/Intersection1.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Deterministic_finite_automaton |
| is dbo:wikiPageDisambiguates of | dbr:DFA |
| is dbo:wikiPageRedirects of | dbr:Myhill_graph dbr:Deterministic_Finite_Automaton dbr:Deterministic_finite_automata dbr:DFA_(computer_science) dbr:Deterministic_finite_state_machine dbr:DFSA dbr:Read-only_right_moving_Turing_machines dbr:Local_automata dbr:Read-only_right-moving_Turing_machines dbr:Read-only_right_moving_Turing_Machines dbr:Finite_deterministic_automaton dbr:Deterministic_finite-state_machine dbr:Deterministic_finite_autonoma dbr:Deterministic_finite_state_automaton dbr:Read_only_right_moving_Turing_Machines dbr:Local_automaton |
| is dbo:wikiPageWikiLink of | dbr:Powerset_construction dbr:List_of_computability_and_complexity_topics dbr:List_of_computing_and_IT_abbreviations dbr:Myhill_graph dbr:Myhill–Nerode_theorem dbr:Nondeterministic_finite_automaton dbr:Probabilistic_automaton dbr:Deterministic_Finite_Automaton dbr:Deterministic_finite_automata dbr:Julius_(software) dbr:Regular_expression dbr:Deterministic_algorithm dbr:Deterministic_automaton dbr:Index_of_computing_articles dbr:Induction_of_regular_languages dbr:Intersection_non-emptiness_problem dbr:Semigroup_action dbr:Weighted_automaton dbr:Computability dbr:Generalized_nondeterministic_finite_automaton dbr:Quantum_finite_automaton dbr:Timeline_of_algorithms dbr:Coco/R dbr:GOLD_(parser) dbr:Configuration_graph dbr:Constraint_(mathematics) dbr:Thompson's_construction dbr:Apache_SpamAssassin dbr:Chomsky–Schützenberger_representation_theorem dbr:Suffix_automaton dbr:Comparison_of_parser_generators dbr:Determinism_(disambiguation) dbr:Krohn–Rhodes_theory dbr:Tagged_Deterministic_Finite_Automaton dbr:McNaughton's_theorem dbr:Mealy_machine dbr:Occam_learning dbr:Büchi_automaton dbr:Tree_automaton dbr:Trie dbr:Garden_of_Eden_(cellular_automaton) dbr:DFA dbr:Jewels_of_Stringology dbr:Local_language_(formal_language) dbr:Semiautomaton dbr:Academic_Torrents dbr:DFA_(computer_science) dbr:DFA_minimization dbr:Edge_coloring dbr:Alphabet_(formal_languages) dbr:Alternating_finite_automaton dbr:Finite-state_transducer dbr:Flex_(lexical_analyser_generator) dbr:Partition_refinement dbr:Chvátal–Sankoff_constants dbr:Floyd–Warshall_algorithm dbr:Deterministic_finite_state_machine dbr:Quantum_Turing_machine dbr:Regular_language dbr:Replication_(computing) dbr:Grigore_Moisil dbr:Counter_(digital) dbr:State_diagram dbr:State_complexity dbr:Cobham's_theorem dbr:Eight-to-fourteen_modulation dbr:Star_height_problem dbr:ReDoS dbr:Read-only_Turing_machine dbr:Automatic_sequence dbr:Free_monoid dbr:DFSA dbr:Kleene_algebra dbr:Brzozowski_derivative dbr:Re2c dbr:Read-only_right_moving_Turing_machines dbr:Separating_words_problem dbr:Mathematical_model dbr:Turing_machine dbr:Unambiguous_finite_automaton dbr:Nested_word dbr:Local_automata dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Queue_automaton dbr:SableCC dbr:Read-only_right-moving_Turing_machines dbr:Read-only_right_moving_Turing_Machines dbr:Finite-state_machine dbr:Permutation_automaton dbr:Word_Processing_in_Groups dbr:Warren_Gish dbr:Two-way_finite_automaton dbr:String_generation dbr:String-searching_algorithm dbr:Finite_deterministic_automaton dbr:Deterministic_finite-state_machine dbr:Deterministic_finite_autonoma dbr:Deterministic_finite_state_automaton dbr:Read_only_right_moving_Turing_Machines dbr:Local_automaton |
| is foaf:primaryTopic of | wikipedia-en:Deterministic_finite_automaton |
