TechCodeview

• NFA steht für nichtdeterministische endliche Automaten. Für eine bestimmte reguläre Sprache ist es einfacher, einen NFA als einen DFA zu erstellen.
• Die endlichen Automaten werden NFA genannt, wenn es viele Pfade für bestimmte Eingaben vom aktuellen Zustand zum nächsten Zustand gibt.
• Nicht jede NFA ist DFA, aber jede NFA kann in DFA übersetzt werden.
• NFA ist auf die gleiche Weise wie DFA definiert, enthält jedoch mit den folgenden zwei Ausnahmen mehrere nächste Zustände und einen ε-Übergang.

In der folgenden Abbildung können wir sehen, dass es ab Zustand q0 für Eingabe a zwei nächste Zustände q1 und q2 gibt, und ähnlich sind ab q0 für Eingabe b die nächsten Zustände q0 und q1. Somit ist nicht festgelegt oder festgelegt, wohin bei einer bestimmten Eingabe als nächstes zu gehen ist. Daher wird dieser FA als nichtdeterministische endliche Automaten bezeichnet.

Formale Definition von NFA:

NFA verfügt ebenfalls über fünf Zustände wie DFA, jedoch mit unterschiedlichen Übergangsfunktionen, wie folgt:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

Wo,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Grafische Darstellung einer NFA

Ein NFA kann durch Digraphen dargestellt werden, die als Zustandsdiagramm bezeichnet werden. In welchem:

1. Der Staat wird durch Eckpunkte dargestellt.
2. Der mit einem Eingabezeichen beschriftete Bogen zeigt die Übergänge.
3. Der Ausgangszustand ist mit einem Pfeil markiert.
4. Der Endzustand wird durch den Doppelkreis gekennzeichnet.

Beispiel 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

Lösung:

Übergangsdiagramm:

So schließen Sie den Entwicklermodus

Übergangstabelle:

Im obigen Diagramm können wir sehen, dass, wenn der aktuelle Zustand q0 ist, bei Eingang 0 der nächste Zustand q0 oder q1 sein wird und bei Eingang 1 der nächste Zustand q1 sein wird. Wenn der aktuelle Zustand q1 ist, ist der nächste Zustand bei Eingang 0 q2 und bei Eingang 1 ist der nächste Zustand q0. Wenn der aktuelle Zustand q2 ist, ist der nächste Zustand bei 0-Eingabe q2, und bei 1-Eingabe ist der nächste Zustand q1 oder q2.

Beispiel 2:

NFA mit ∑ = {0, 1} akzeptiert alle Strings mit 01.

Java wandelt int in einen String um

Lösung:

Übergangstabelle:

Beispiel 3:

NFA mit ∑ = {0, 1} und akzeptieren Sie alle Zeichenfolgen mit einer Länge von mindestens 2.

Lösung:

Übergangstabelle: