Unterschied zwischen NFA und DFA?
Hallo, kann mir jemand sagen wo man DFA's anwendet und wo NFA's? ich kenne die unterschiede doch verstehe den sinn nicht warum man nicht gleich nur eins nutzt und man beide beigebracht bekommt. Was ist der Sinn, wo brauche ich nfa und wo dfa?
Danke wenn mir jemand helfen kann :D
1 Antwort
NFA sind nicht-deterministische Automaten und DFA sind deterministische Automaten. Deterministisch heißt hier, dass aus einem beliebigem Zustand zu jedem Zeichen nur genau ein Übergang in genau einen anderen Zustand existiert.
NFAs können für das gleiche Zeichen verschiedene Übergänge vom selben Zustand aus definieren.
NFA sind teilweise leichter zu konstruieren, da man sich gewisse Dinge der Sprache nicht so gut vorstellen kann.
Man kann aber alle NFAs in DFAs umwandeln, denn nur DFAs können effizient von Computern berechnet werden. Das ganze nennt sich die Potenzmengenkonstruktion (hatten wir im Studium auch als Potenzmengenautomat geführt). Es gibt einen recht einfachen Algorithmus dazu!