Formale Sprachen NFA und DFA?
In der Regel geht man so vor, das man aus einer Sprache L(G) mit einer Grammatik einen NFA(Nichtdeterministischen Automaten) konstruiert. Dann aus dem NFA eine DFA (Deterministischen Automaten) und daraus wieder die Sprache mit Ihrer Grammatik ableitet L(G).
L(G) zu NFA zu DFA zu LG?
Was ich mich jetzt Frage ist, kann man auch anders herum vorgehen, d. h. man aus einer L(G) einen DFA und aus diesem dann einen NFA und daraus leitet man wieder seine Grammatik ab?
Oder ist diese Vorgangsweise um einiges komplizierter als von
LG zu DFA zu NFA zu LG
1 Antwort
Ein DFA ist ein NFA. Mir ist auch nicht ganz klar, was genau jetzt der Unterschied zwischen dem erstem L und dem zweitem L sein soll. Aber man kann die in beide Richtungen umwandeln, sind ja äquivalent.
Du kannst natürlich auch direkt von L(G) zum DFA gehen. Musst dir halt dann im Kopf mehr denken.
Du kannst alles in alles umwandeln, das zeigt sich ja durch den Kreislauf.
Und wie macht man bitte aus einem DFA einen NFA?
Jeder DFA ist auch ein NFA.
Weng verwirrend aber ok. Und jeder NFA ist auch ein DFA. Richtig?
Und jeder NFA ist auch ein DFA. Richtig?
Nein.
Ein NFA kann Epsilonübergänge und dergleichen haben. Das darf ein DFA nicht haben.
Aber jeder NFA lässt sich (mittels Potenzmengenkonstruktion) in einen DFA umwandeln.
Das L(G) ist immer die gleiche Sprache mit der selben Grammatik!
Warum wandelt man in der Regel von L(G) zu NFA zu DFA zu L(G) wieder um.
Ist ja wie ein Kreislauf
Warum geht man nicht von L(G) zu DFA zu NFA zu L(G)
Das ist meine Frage. Ist dieser Weg komplizierter?
Und wie macht man bitte aus einem DFA einen NFA?
Wir haben immer nur von einem NFA in einen DFA umgewandelt.