| dbo:abstract
|
- In der Informatik ist ein Zweiwege deterministischer endlicher Automat (Zweiwege-DFA, 2DFA) ein Automat, genauer gesagt ein deterministischer endlicher Automat (DFA), der bereits gelesene Zeichen noch einmal besuchen kann. Wie im DFA gibt es auch im 2DFA eine endliche Anzahl an Zuständen, die durch Transitionen unter Beachtung des zu lesenden Zeichens miteinander verbunden sind. Darüber hinaus ist jede Transition auch mit der Information gekennzeichnet, ob der Automat seine Leseposition nach links oder nach rechts ändert. 2DFAs können demnach auch als schreibgeschützte Turingmaschine mit nur lesbarem Eingabeband betrachtet werden. Für 2DFAs kann man zeigen, dass sie dieselbe Mächtigkeit haben wie DFAs; das heißt, jede formale Sprache, die von einem 2DFA erkannt wird, kann auch von einem DFA, der lediglich alle Zeichen in der Reihenfolge abarbeitet, erkannt werden. Da DFAs offensichtlich ein Spezialfall der 2DFAs sind, erkennen beide Automaten genau die Menge der regulären Sprachen. Jedoch kann der zum 2DFA äquivalente DFA exponentiell mehr Zustände haben, was den 2DFA für Algorithmen einiger Grundprobleme um einiges praktischer macht. Sie sind auch äquivalent zu schreibgeschützten Turingmaschinen, die nur eine gleichbleibende Menge an Platz auf dem Arbeitsband haben, da jede konstante Menge an Information in den endlichen Kontrollzustand über eine Produktbildung eingebracht werden kann (ein Zustand für jede Kombination von Arbeitsband und Kontrollzustand). Das Konzept der 2DFAs geht auf Michael O. Rabins und Dana Scotts Arbeit Finite automata and their decision problems zurück und wurde 1997 von John Watrous' On the Power of 2-Way Quantum Finite State Automata zu Quantenautomaten verallgemeinert, in der er zeigt, dass diese Automaten auch nichtreguläre Sprachen erkennen können und somit noch mächtiger sind als 2DFAs. (de)
- En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais « two-way deterministic finite automaton ») souvent abrégé en 2AFD (en anglais 2DFA), est un automate fini déterministe qui peut relire des symboles d'entrée déjà vus. Comme pour les automates finis déterministes usuels, un 2AFD possède un nombre fini d'états, et le passage d'un état à un autre est régi par des transitions en fonction du symbole lu. De plus, une transition porte une information sur la direction de déplacement de la lecture, soit vers la droite soit vers la gauche. Un automate bidirectionnel peut donc être vu comme une machine de Turing qui ne peut pas écrire sur sa bande de données et qui ne dispose pas de mémoire auxiliaire. (fr)
- In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input. (en)
- Em Ciência da Computação, em particular em Teoria dos Autômatos, um autômato é chamado two-way se é permitido reler sua entrada. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11839 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:reason
|
- 'L' and 'R' are not allowed in the 2nd component of a \delta result. Probably, in the right hand side of the following 4 equations, 'L' should be fixed to 'left' and 'R' to 'right'? (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais « two-way deterministic finite automaton ») souvent abrégé en 2AFD (en anglais 2DFA), est un automate fini déterministe qui peut relire des symboles d'entrée déjà vus. Comme pour les automates finis déterministes usuels, un 2AFD possède un nombre fini d'états, et le passage d'un état à un autre est régi par des transitions en fonction du symbole lu. De plus, une transition porte une information sur la direction de déplacement de la lecture, soit vers la droite soit vers la gauche. Un automate bidirectionnel peut donc être vu comme une machine de Turing qui ne peut pas écrire sur sa bande de données et qui ne dispose pas de mémoire auxiliaire. (fr)
- In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input. (en)
- Em Ciência da Computação, em particular em Teoria dos Autômatos, um autômato é chamado two-way se é permitido reler sua entrada. (pt)
- In der Informatik ist ein Zweiwege deterministischer endlicher Automat (Zweiwege-DFA, 2DFA) ein Automat, genauer gesagt ein deterministischer endlicher Automat (DFA), der bereits gelesene Zeichen noch einmal besuchen kann. Wie im DFA gibt es auch im 2DFA eine endliche Anzahl an Zuständen, die durch Transitionen unter Beachtung des zu lesenden Zeichens miteinander verbunden sind. Darüber hinaus ist jede Transition auch mit der Information gekennzeichnet, ob der Automat seine Leseposition nach links oder nach rechts ändert. 2DFAs können demnach auch als schreibgeschützte Turingmaschine mit nur lesbarem Eingabeband betrachtet werden. (de)
|
| rdfs:label
|
- Zweiwege-DFA (de)
- Automate fini déterministe bidirectionnel (fr)
- Autômato finito determinístico de dois sentidos (pt)
- Two-way finite automaton (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
