Nichtdeterministischer endlicher Automat

Schlüsselelemente eines nichtdeterministischen endlichen Automaten

// Ein einfacher nichtdeterministischer endlicher Automat
final NFA nfa = new NFA(
    Set.of(State.START, State.ACCEPT, State.DEAD),
    Set.of('a', 'b'),
    Set.of(
        new Transition(State.START, 'a', State.START),
        new Transition(State.START, 'b', State.ACCEPT),
        new Transition(State.ACCEPT, 'a', State.DEAD),
        new Transition(State.ACCEPT, 'b', State.DEAD)
    ),
    State.START,
    Set.of(State.ACCEPT)
);

Beispiele für einen nichtdeterministischen endlichen Automaten

Es ist oft hilfreich, abstrakte Konzepte anhand konkreter Beispiele zu demonstrieren. Daher werden in diesem Abschnitt zwei Beispiele für nichtdeterministische endliche Automaten vorgestellt. Diese Beispiele variieren in ihrer Komplexität, um ein breites Verständnis des Konzepts zu ermöglichen.

Einfaches Beispiel: Erkennen eines nichtdeterministischen endlichen Automaten

// Ein einfacher nichtdeterministischer endlicher Automat
NFA simpleNFA = new NFA(
    Set.of("q0", "q1", "q2"),    // Zustände
    Set.of('a', 'b'),            // Eingabealphabet
    Map.of(                     // Übergangsfunktion
        "q0", Map.of('a', "q1"),
        "q1", Map.of('b', "q2")
    ),
    "q0",                       // Startzustand
    Set.of("q2")                // Akzeptierende Zustände
);

Komplexeres Beispiel: Nichtdeterministischer endlicher Automat im Einsatz

//Ein komplexerer nichtdeterministischer endlicher Automat
NFA complexNFA = new NFA(
    Set.of("q0", "q1", "q2", "q3", "q4"),    // Zustände
    Set.of('a', 'b'),                         // Eingabealphabet
    Map.of(                                  // Übergangsfunktion
        "q0", Map.of('a', Set.of("q1", "q3")),
        "q1", Map.of('b', "q2"),
        "q3", Map.of('b', "q4")
    ),
    "q0",                                    // Startzustand
    Set.of("q2", "q4")                       // Akzeptierende Zustände
);

Von einem nichtdeterministischen endlichen Automaten zu einem deterministischen endlichen Automaten

Der Konversionsprozess verstehen

Unterschiede zwischen nichtdeterministischen und deterministischen endlichen Automaten

• Im DEA verbindet für jeden Zustand und jedes Eingabesymbol genau eine Übergangsregel den Zustand mit genau einem anderen Zustand.
• Im Gegensatz dazu kann ein NEA für einen bestimmten Zustand und ein Eingabesymbol mehrere Übergänge zu verschiedenen Zuständen haben. Außerdem können NEAs ε-Übergänge haben, bei denen der Automat den Zustand wechseln kann, ohne ein Eingabesymbol zu verbrauchen.

• \(Q\) ist eine endliche Menge von Zuständen.
• \(Σ\) ist eine endliche Menge namens Alphabet.
• \(δ : Q × Σ → Q\) ist die Übergangsfunktion.
• \(q0 ∈ Q\) ist der Startzustand.
• \(F ⊆ Q\) ist die Menge der akzeptierenden Zustände.

• \(Q\) ist eine endliche Menge von Zuständen.
• \(Σ\) ist eine endliche Menge namens Alphabet.
• \(Δ: Q × Σ∪{ε} → P(Q)\) ist die Übergangsfunktion.
• \(q0 ∈ Q\) ist der Startzustand.
• \(F ⊆ Q\) ist die Menge der akzeptierenden Zustände.

Nichtdeterministischer endlicher Automat in Java

1. Erstellen der Zustände und des Alphabets: Zuerst werden die Zustände des Automaten und das verwendete Alphabet definiert. Dies kann durch Java-Listen oder -Sets geschehen. Beispielsweise könnte das Alphabet durch die Zeichen 'a' und 'b' definiert sein und die Zustände könnten durch Zeichenfolgen wie "q0", "q1" usw. repräsentiert werden.
2. Definition der Übergangsfunktion: Die Übergangsfunktion bestimmt, wie der Automat von einem Zustand zum nächsten wechselt. Sie wird oft durch eine Map dargestellt. Jeder Zustand kann dabei auf eine weitere Map verweisen, die für jedes Symbol des Alphabets den nächsten Zustand oder die nächsten Zustände angibt.
3. Bestimmung des Startzustands und der akzeptierenden Zustände: Der Startzustand und die akzeptierenden Zustände sind wichtige Teile eines NEA und werden ebenfalls definiert.
4. Erstellen einer Funktion zur Überprüfung von Eingabewörtern: Schließlich wird eine Funktion benötigt, die ein Eingabewort überprüft, indem sie den Automaten Schritt für Schritt durch die Zeichen des Wortes führt. Sie startet im Startzustand und führt für jedes Zeichen des Wortes die entsprechenden Zustandswechsel durch. Wenn der Automat am Ende des Wortes in einem akzeptierenden Zustand ist, wird das Wort akzeptiert, sonst abgelehnt.

Codierungsbeispiele

import java.util.*;

class NFA {
    private Set states;
    private Set alphabet;
    private Map>> transitionFunction;
    private String startState;
    private Set acceptStates;

    // Konstruktor
    public NFA(Set states, Set alphabet, 
               Map>> transitionFunction, 
               String startState, Set acceptStates){
        this.states = states;
        this.alphabet = alphabet;
        this.transitionFunction = transitionFunction;
        this.startState = startState;
        this.acceptStates = acceptStates;
    }

    public boolean accept(String word){
        Set currentStates = new HashSet<>();
        currentStates.add(startState);

        for(char c : word.toCharArray()){
            Set nextStates = new HashSet<>();
            for(String state : currentStates){
                if(transitionFunction.get(state).containsKey(c)){
                    nextStates.addAll(transitionFunction.get(state).get(c));
                }
            }
            
            if(nextStates.isEmpty()){
                return false;
            }
            
            currentStates = nextStates;
        }
        
        currentStates.retainAll(acceptStates);
        
        return !currentStates.isEmpty();
    }
}

Minimierung von nichtdeterministischen endlichen Automaten

Das Prinzip der Minimierung: Verkleinerung der Anzahl der Zustände

Beispiele für die Minimierung eines nichtdeterministischen endlichen Automaten

// Ein einfacher nichtdeterministischer endlicher Automat
NFA simpleNFA = new NFA(
    Set.of("q0", "q1", "q2", "q3"),    // Zustände
    Set.of('a', 'b'),              // Eingabealphabet
    Map.of(                       // Übergangsfunktion
        "q0", Map.of('a', Set.of("q1", "q2")),
        "q1", Map.of('b', "q3"),
        "q2", Map.of('b', "q3"),
        "q3", Map.of('a', "q0")
    ),
    "q0",                         // Startzustand
    Set.of("q3")                  // Akzeptierende Zustände
);

// Der resultierende deterministische endliche Automat
DFA simpleDFA = new DFA(
    Set.of("Q0", "Q1", "Q2"),    // Zustände
    Set.of('a', 'b'),            // Eingabealphabet
    Map.of(                     // Übergangsfunktion
        "Q0", Map.of('a', "Q1"),
        "Q1", Map.of('b', "Q2"),
        "Q2", Map.of('a', "Q0")
    ),
    "Q0",                       // Startzustand
    Set.of("Q2")                // Akzeptierende Zustände
);