7
Kann nichts bejahendes finden. Und ein NFA mit einem Epsilon-Übergang ist ein Epsilon-NFA? Danke.Kann ein DFA epsilon/lambda-Übergänge haben?
A
Antwort
9
DFA hat keine epsilon-Übergänge. Wenn es es hätte, könnte es vom aktuellen Zustand in einen anderen Zustand ohne irgendeine Eingabe übergehen, d. H. Mit nichts, nicht einmal {} oder phi. Und als Definition wissen wir, dass die Eingabe von der Eingabesatz stammen muss. Hoffe, das löste Ihre Zweifel ...
+0
Was wäre, wenn dieser Übergang zu einem Endzustand wäre? Wie Abbildung 3.51 auf Seite 225 dieses Dokuments http://www.univasf.edu.br/~marcus.ramos/lfa-2008-1/Secao%2003-06.pdf. – liwing
+0
Wow..das Bild ist selbsterklärend jetzt..wie Sie sehen, Q0 Transits zu Q3 ohne Eingabe und daher ist es NFA und es hat Epsilon bewegt, so ist es Epsilon-NFA und nicht die DFA .. –
+0
Danke für die Klarstellung – liwing
2
DFA muss ein bestimmtes Eingabesymbol haben, um von einem Zustand in einen anderen Zustand zu wechseln. Epsilon move ist in DFA nicht zulässig, da DFA in NFA geändert wird. Angenommen, Sie befinden sich im Status Q1 und Sie haben einen Übergang (Q1, e) = Q2. In diesem Fall können Sie direkt zu Q2 wechseln, ohne eine Eingabe zu machen. Sie können auch im Q1-Status bleiben im Zustand Q1. Im Falle von DFA dürfen Sie keine Auswahlkriterien haben. Aus diesem Grund haben DFA keine Epsilon-Züge.
2
Aus der Definition von DFA, "Deterministische Finite Automata ist eine Maschine, die nicht auf anderen Zustand bewegen kann, ohne irgendeine Eingabe zu erhalten." Und da Epsilon bedeutet nichts. Daher kann DFA nicht auf Epsilon Bewegungen bewegt werden.
Während von der Definition von NFA, "Nicht deterministische Finite Automata ist eine Maschine, die auf anderen Zustand bewegen kann, ohne irgendwelche Eingaben zu bekommen." So NFA kann auf Epsilon bewegt sich bewegen.
Was meinen Sie mit Lambda-Übergang? –
Einige Bücher verwenden Lambda anstelle von Epsilon. Das ist gleich. – liwing