| dbpprop:abstract
|
- In the theory of computation, a deterministic finite state machine (also known as deterministic finite state automaton or deterministic finite automaton) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. DFAs recognize the set of regular languages and no other languages. A DFA will take in a string of input symbols. For each input symbol it will then transition to a state given by following a transition function. When the last input symbol has been received it will either accept or reject the string depending on whether the DFA is in an accepting state or a non-accepting state.
- Ein deterministischer endlicher Automat ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (mögliche Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Formal kann ein DEA <math>\mathcal{A}</math> als 5-Tupel <math>\left(Q, \Sigma, \delta, q_0, F \right)</math> definiert werden. Hierbei gilt Folgendes: <math>Q</math> (oft auch <math>Z</math> oder <math>S</math>) ist eine Zustandsmenge, eine nichtleere endliche Menge von Zuständen. Zum Beispiel z0, z1 und z2 oder auch „Getränkeautomat wartet auf Eingabe“, „Kaffee ausschenken“, „Wechselgeld zurückgeben“, … <math>\Sigma</math> ist ein endliches Eingabealphabet, also erlaubte Eingaben, wie z. B. 1 und 0 oder auch „Münze einwerfen“, „Taste für Milchkaffee drücken“, „Taste Abbruch drücken“, … Es gibt eine Übergangsfunktion <math>\delta : Q \times \Sigma \rightarrow Q</math>, so dass für <math>p, q \in Q</math> und <math>a \in \Sigma</math> gilt <math>\delta(q, a) = p</math>. <math>\delta</math> ordnet jedem Paar, bestehend aus einem Zustand <math>q</math> und einem Eingabesymbol <math>a</math>, einen neuen Zustand <math>p</math> zu. Der Automat wechselt also von einem Zustand <math>q</math> in einen anderen Zustand <math>p</math>, wenn im Zustand <math>q</math> eine (gültige) Eingabe <math>a</math> gemacht wurde. Beispiel: <math>\delta</math>(z0, 1) = z2 oder <math>\delta</math>(„Getränkeautomat wartet auf Eingabe“, „Taste für Milchkaffe gedrückt“) = "Kaffee ausschenken" <math>q_0 \in Q </math> ist der Startzustand. Statt <math>q_0</math> wird oft auch <math>z_0</math> verwendet. Beispiel: z0 oder „Getränkeautomat wartet auf Eingabe“. <math>F \subseteq Q</math> (oft auch <math>A</math>) ist die Menge der akzeptierenden Zustände, die sogenannten Finalzustände. Zum Beispiel: z2 oder „Getränkeautomat wartet auf Eingabe“ (in diesem Fall ist der Startzustand auch ein Finalzustand) Wenn sich der Automat nach dem Lesen des Eingabewortes <math>w \in \Sigma^*</math>, also einer Folge von Eingaben und den damit verbundenen Zustandsübergängen, in einem Finalzustand aus <math>F</math> befindet, so gehört <math>w</math> zur Sprache <math>L\left(\mathcal{A}\right)</math>. Ist ein DEA in der Lage jedes Wort über dem betrachteten Alphabet bis zum Ende lesen zu können, auch wenn es nicht in der zu akzeptierenden Sprache enthalten ist, wird er vollständig genannt. Nichtdeterministische endliche Automaten (NEAs), DEAs und Typ-3-Grammatiken beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs wandeln.
- Un autómata finito determinista o AFD es un modelo compuesto de un número finito de estados, transiciones entre los estados y acciones.
- A számítógép-tudományban a determinisztikus véges állapotú gép vagy determinisztikus véges állapotú automata egy véges állapotú gép, ahol minden állapot–bejövő szimbólum párhoz egy és csakis egy másik állapotba való átmenet tartozik. A DFA a szabályos nyelvek halmazába tartozó nyelvek felismerésénél használható, más nyelveknél nem alkalmazható. A DFA egy bejövő szimbólumokból álló stringgel dolgozik. Minden egyes bejövő szimbólum hatására a gép állapota az adott átmeneti függvény alapján megváltozik (vagy ugyanaz marad). Amikor az utolsó bejövő szimbólum beérkezik, azt a gép állapotától függően vagy elfogadják vagy visszautasítják. A DFA-t tekinthetjük egy speciális Turing-gépnek, amely nem tudja az olvasófejet mozgatni, és csak előre képes mozgatni a szalagját.
- 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.
- 決定性有限オートマトン（けっていせい-、Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受容状態であれば入力文字列は受容されたと判断され、受容状態でなければ入力文字列は拒否されたと判断される。
- 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.
- 在计算理论中，确定有限状态自动机或确定有限自动机（英：deterministic finite automaton；简称：DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表<math>\Sigma</math>的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态有可能就是先前那个状态）。
|
| rdfs:comment
|
- In the theory of computation, a deterministic finite state machine (also known as deterministic finite state automaton or deterministic finite automaton) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. DFAs recognize the set of regular languages and no other languages. A DFA will take in a string of input symbols. For each input symbol it will then transition to a state given by following a transition function.
- Ein deterministischer endlicher Automat ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (mögliche Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Formal kann ein DEA <math>\mathcal{A}</math> als 5-Tupel <math>\left(Q, \Sigma, \delta, q_0, F \right)</math> definiert werden.
- Un autómata finito determinista o AFD es un modelo compuesto de un número finito de estados, transiciones entre los estados y acciones.
- A számítógép-tudományban a determinisztikus véges állapotú gép vagy determinisztikus véges állapotú automata egy véges állapotú gép, ahol minden állapot–bejövő szimbólum párhoz egy és csakis egy másik állapotba való átmenet tartozik. A DFA a szabályos nyelvek halmazába tartozó nyelvek felismerésénél használható, más nyelveknél nem alkalmazható. A DFA egy bejövő szimbólumokból álló stringgel dolgozik.
- 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.
- 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.
- 在计算理论中，确定有限状态自动机或确定有限自动机（英：deterministic finite automaton；简称：DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表<math>\Sigma</math>的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态有可能就是先前那个状态）。
|
![[RDF Data]](/statics/sw-cube.png)
