Deterministischer Endlicher Automat

Dieses Dokument wurde erstellt von Stefan Kühnel stefan.kuehnel@hm.edu und Hubert Fuchs hfuchs@hm.edu

1. Abstrakt

Deterministische Endliche Automaten (DFA) können in vielen verschiedenen Anwendungsgebieten eingesetzt werden. Dazu zählen beispielsweise die Analyse von Mustern in Daten (vgl. Justin et. al. 2017, S. 1) [Ref 1], die Verarbeitung von Wörtern in der theoretischen Informatik (vgl. Javier 2017, S. 18 f.) [Ref 2] oder auch die Modellierung von Vertragsabläufen bei finanziellen Kontrakten (vgl. Flood et. al. 2015, S. 3) [Ref 3].

Im Folgenden wird daher ein allgemeiner endlicher Automat definiert und implementiert, der es unter anderem ermöglicht, einen beliebigen Ausdruck zu erfassen und gemäß vorgegebenen Regeln zu verarbeiten. Um dabei eine effiziente Verwaltung von Zustandsübergängen zu ermöglichen, wird bei der Implementierung ein besonders hohes Augenmerk auf die Verwendung geeigneter Datenstrukturen gelegt. Hierbei sollen unter anderem die Python-Datentypen list und dict konkreter analysiert werden. Ferner wird zur Visualisierung und zu Veranschaulichungszwecken eine Möglichkeit bereitgestellt, den DFA als zweidimensionalen Graphen auszugeben.

Zum Abschluss wird, um den Sinn und die Einsatzzwecke endlicher Automaten zu verdeutlichen, ein konkreter endlicher Automat zur Steuerung einer Kaffeemaschine implementiert. Dabei wird das Anwendungsbeispiel so minimal und so wenig komplex wie möglich gehalten, um eine Erweiterung auf anderer Anwendungsgebiete auch weiterhin zu ermöglichen.

2. Theoretisches Modell

2.1. Implementierung eines allgemeinen endlichen Automaten

Ein endlicher Automat wird grundsätzlich als ein Fünf-tupel definiert: $\mathrm {A} = \left(Z,\,\Sigma ,\,\delta ,\,z_{0},\,E\right)$

Dabei entspricht $Z$ der Menge aller Zustände, in denen sich der Automat währen der Abarbeitung eines Wortes befinden kann. Der Startzustand $z_{0} \in Z$ legt fest, in welchem Zustand der Automat sich zu Beginn der Abarbeitung des Wortes $w$ befinden soll. Das endliche Eingabealphabet $\Sigma$ legt anschließend fest, welche Symbole in der Eingabe vorhanden sein dürfen.

In welchen Folgezustand der Automat wechselt, wenn er eine bestimmtes Symbol der Eingabe erhält, wird durch die $\delta$-Funktion beschrieben. Grundlegend handelt es sich dabei um eine Funktion, die einen Zustand der Menge $Z$ und ein Symbol der Menge $\Sigma$ auf einen Folgezustand der Menge $Z$ abbildet. Die $\delta$-Funktion ist deshalb definiert als: $\delta: Z \times \Sigma \rightarrow Z$

Die Menge $E \subseteq Z$ umfasst schließlich die Menge aller akzeptierten Endzustände. Befindet sich ein endlicher Automat nach Abarbeitung der Eingabe in einem Zustand $z_{0} \in E$, so wird das Wort akzeptiert. Befindet er sich nicht in einem solchen Zustand, so wird das übergebene Wort nicht akzeptiert. (vgl. Boockmeyer et. al. 2018, S. 198 ff.) [Ref 4]

In [1]:
class ListConverter():
    def __init__(self, config):
        """
        Erstellt einen ListConverter, der die folgenden Konfigurationseinheiten in eine Listenstruktur konvertiert.
        config["states"] = Eine endliche Zustandsmenge.
        config["alphabet"] = Ein endliches Eingabealphabet mit Symbolen.
        config["transitions"] = Eine Zustand-Folgezustand-Tabelle. 
        """        
        self.states = config["states"]
        self.alphabet = config["alphabet"]
        self.transitions = config["transitions"]
        
        self.to_list()
        
    def to_list(self):
        """
        Führt alle Konvertierungsschritte aus.
        """
        self.alphabet_to_list()
        self.states_to_list()
        self.transitions_to_list()
        
    def alphabet_to_list(self):
        """
        Konvertiert das Alphabet in eine sortierte Liste.
        """
        alphabet_list = list(self.alphabet)
        alphabet_list.sort()
        
        self.alphabet = alphabet_list
        
    def states_to_list(self):
        """
        Konvertiert die Zustände in eine sortierte Liste.
        """
        states = self.states
        number_of_states = len(states)
        states_list = [0 for i in range(number_of_states)]  # Erstellung einer mit 0 initialisierten Liste fester Größe.
        for state in states:
            state_index = int(state[1]) - 1  # Der numerische Index n jedes Zustands z_n
            states_list[state_index] = state
            
        self.states = states_list
        
    def transitions_to_list(self):
        """
        Konvertiert Zustand-Folgezustand-Tabelle in eine Liste.
        """
        transitions = self.transitions
        alphabet = self.alphabet
        states = self.states
        
        # Umformung der Zustand-Folgezustand-Tabelle in eine sortierte Liste.        
        transitions_list = []
        for state_transition in transitions.values():
            subsequent_states = []
            for symbol in alphabet:
                subsequent_state = state_transition[symbol]  # Der Folgezustand für ein Zeichen.
                subsequent_state_index = states.index(subsequent_state)  # Ermittlung des Indexes des Folgezustands
                subsequent_states.append(subsequent_state_index)  # Speichern des Indexes des Folgezustands

            transitions_list.append(subsequent_states)  # Speichert alle Folgezustände für alle Zeichen eines bestimmten Zustandes
        self.transitions = transitions_list
        
    def get_alphabet(self):
        """
        Gibt das konvertierte Alphabet zurück.
        """
        return self.alphabet
    
    def get_states(self):
        """
        Gibt die konvertierte Zustandsliste zurück.
        """
        return self.states
    
    def get_transitions(self):
        """
        Gibt die konvertierte Zustand-Folgezustand-Tabelle zurück.
        """
        return self.transitions
        
class DFA():
    def __init__(self, config):
        """
        Initialisiert einen neuen endlichen Automaten.
        config["states"] = Eine endliche Zustandsmenge.
        config["alphabet"] = Ein endliches Eingabealphabet mit Symbolen.
        config["transitions"] = Eine Zustand-Folgezustand-Tabelle.
        config["start_state"] = Ein Startzustand, Element der endlichen Zustandsmenge.
        config["end_states"] = Eine Menge endlicher Endzustände, Teilmenge der endlichen Zustandsmenge.
        """
        assert("states" in config), "Bitte übergeben Sie eine endliche Zustandsmenge."
        assert("alphabet" in config), "Bitte übergeben Sie ein endliches Eingabealphabet."
        assert("transitions" in config), "Bitte übergeben Sie eine Zustand-Folgezustand-Tabelle."
        assert("start_state" in config), "Bitte übergeben Sie einen Startzustand."
        assert("end_states" in config), "Bitte übergeben Sie eine Menge endlicher Endzustände."
        
        assert(type(config["states"]) == set), "Die endliche Zustandsmenge muss den Typ 'set' besitzen."
        assert(type(config["alphabet"]) == set), "Das Endliche Eingabealphabet muss den Typ 'set' besitzen."
        assert(type(config["transitions"]) == dict), "Die Zustand-Folgezustand-Tabelle muss den Typ 'dict' besitzen."
        assert(type(config["start_state"]) == str), "Der Startzustand muss den Typ 'str' besitzen."
        assert(type(config["end_states"]) == set), "Die Menge endlicher Endzustände muss den Typ 'set' besitzen."
        
        assert(config["start_state"] in config["states"]), "Der Startzustand muss Element der endlichen Zustandsmenge sein."
        assert(config["end_states"].issubset(config["states"])), "Die Menge endlicher Endzustände muss eine Teilmenge der endlichen Zustandsmenge sein."
        
        self.states = config["states"]
        self.alphabet = config["alphabet"]
        self.transitions = config["transitions"]
        self.start_state = config["start_state"]
        self.end_states = config["end_states"]
        self.list_usage = False
        
        self.config = config
    
    def use_list(self):
        """
        Konvertiert das Eingabeset der Zustand-Folgezustand-Tabelle in eine Liste.
        """
        self.list_usage = True
            
        list_converter = ListConverter(self.config)
        self.alphabet_list = list_converter.get_alphabet()
        self.states_list = list_converter.get_states()
        self.transitions_list = list_converter.get_transitions() 
    
    def run(self, word):
        """
        Arbeitet ein übergebenes Wort gemäß den in der Basiskonfiguration gemachten Angaben ab.
        word = Ein Wort bestehend aus Symbolen des endlichen Eingabealphabets.
        """
        word_chars = set(word)
        assert(word_chars.issubset(self.alphabet)), "Übergebenes Wort enthält Zeichen, die nicht Element des Eingabealphabets sind."
        
        if(self.list_usage):
            # Setzen des aktuellen Zustands auf den Startzustand
            current_state = self.states_list.index(self.start_state)

            # Durchlaufen der Zustand-Folgezustand-Tabelle mit jedem einzelnen Zeichen des übergebenen Wortes.
            for char in word:
                char_index = self.alphabet_list.index(char)
                current_state = self.transitions_list[current_state][char_index]

            # Überprüfung, ob der finale Zustand Element der Menge endlicher Endzustände ist.
            return self.states_list[current_state] in self.end_states
        else:
            # Setzen des aktuellen Zustands auf den Startzustand
            current_state = self.start_state
        
            # Durchlaufen der Zustand-Folgezustand-Tabelle mit jedem einzelnen Zeichen des übergebenen Wortes.
            for char in word:
                current_state = self.transitions[current_state][char]

            # Überprüfung, ob finaler Zustand Element der Menge endlicher Endzustände ist.
            return current_state in self.end_states

    def plot(self):
        """
        Erstellt eine zweidimensionale Darstellung des endlichen Automaten gemäß der Basiskonfiguration.
        """
        # Erstellung der Datenkonfiguration des Graphen
        graph_data = [(node, go_to, if_char) for node, connections in self.transitions.items() for if_char, go_to in connections.items()]
        
        # Generierung des Graphen-Objektes
        graph = DiGraph(
            loops=True,
            sparse=True,
            multiedges=True
        )
        
        # Hinzufügen der Datenkonfiguration des Graphen
        graph.add_edges(graph_data)
        
        # Generierung des Graphen-Plots
        plot = graph.graphplot(
            edge_labels=True,
        )
        
        # Ausgabe des Plots
        plot.show()
        
        # Ausgabe der Start-/ und Endzustandsinformationen
        print("Der Startzustand ist: {0}".format(self.start_state))
        print("Die akzeptierten Endzustände sind: {0}".format(self.end_states))

2.2. Effizienzprüfung von Datenstrukturen zur Verwaltung der Zustandsübergänge

Im konkreten Fall wurde zur Verwaltung der Zustandsübergänge auf zwei verschiedene Datenstrukturen, nämlich list und dict zurückgegriffen. Als Ausgangsdatenstruktur kommt dabei das Dictionary zum Einsatz, da es aufgrund der Key-Value-Pairs wesentlich einfacher und intuitiver aufzusetzen bzw. mit Daten zu befüllen ist, als eine Liste.

Die anschließende Umwandlung von dict zu list erfolgt vollständig automatisiert mit Hilfe eines Umwandlungsalgorithmus. Da die Zustände in Form von Strings in das Dictionary geschrieben werden, können die entsprechenden Indizes aus den Zuständen $z_1, z_2, z_3, \dots, z_n$ durch einen arrayähnlichen Zugriff ausgelesen werden.

Beispiel:

Nachfolgend soll der Index des Zustands $z_1$ mit Hilfe von Python ermittelt werden.

In [3]:
state = "z1"

state_index = example_state[1]  # Der Wert an der Position 1 im Zustand entspricht dem Index.

print("Der Index des Zustandes {0} entspricht dem Wert {1}".format(state, state_index))
Der Index des Zustandes z1 entspricht dem Wert 1

Durch diese Vorgehensweise, kann auf die Verwendung eines Tokenizers verzichtet werden, wodurch der Umwandlungsalgorithmus insgesamt erheblich vereinfacht und dadurch auch verständlicher wird.

Bei der Zeitmessung im anschließenden Schritt wurde auf das in Python 3.x Versionen standardmäßig mitgelieferte Zeitmessungswerkzeug timeit zurückgegriffen. Da es unter anderem für kleine Programme entwickelt wurde, eignet es sich daher ideal zum testen der run(word) Methode. [Ref 5]

Da sich bei der Verwendung von kurzen Wörtern jedoch signifikante Laufzeitunterschiede herausstellen, war es erforderlich die run(word) Methode jeweils mit einem sehr langen Wort zu testen, da dadurch kleine Laufzeitunterschiede bei kurzen Wörtern eliminiert werden.

2.3. Erstellung eines konkreten Automaten zur Steuerung einer Kaffeemaschine

Die Konstruktion eines konkreten Automaten zur Steuerung einer Kaffeemaschine erfordert zu allererst die Definition eines geeigneten Eingabealphabets $\Sigma$. Dieses enthält alle erlaubten Operationen, die ein Kunde auf dem Touchscreen des Gerätes ausführen kann. Die endliche Zustandsmenge $Z$ enthält daraus Folgend dann alle resultierenden Zustände, in denen sich die Kaffeemaschine bei der Bedienung durch den Nutzer befinden kann.

Eingabealphabet:

$\Sigma = \{$ Start, Weiter, Zurück, Abbruch, Gewünschter Kaffee, Geld, Geldentnahme, Entnahme des Kaffees $\}$

Endliche Zustandsmenge:

$Z = \{$ Bereitschaft, Menüanzeige, Geldeingabe, Zahlung abschließen?, Zubereitung $\}$

Übergangsfunktion:

Nachfolgend wird die Übergangsfunktion in Form einer Zustand-Folgezustand Tabelle angegeben.

Aktueller Zustand Eingabe Folgezustand
Bereitschaft Start Menüanzeige
Menüanzeige Abbruch Bereitschaft
Menüanzeige Gewünschter Kaffee Geldeingabe
Geldeingabe Zurück Menüanzeige
Geldeingabe Abbruch Bereitschaft
Geldeingabe Geld Zahlung abschließen?
Zahlung abschließen? Weiter Zubereitung
Zahlung abschließen? Abbruch Geldrückgabe
Geldrückgabe Geldentnahme Bereitschaft
Zubereitung Entnahme des Kaffees Bereitschaft

Startzustand:

$z_{0} = $ Bereitschaft

Menge aller akzeptierten Endzustände:

$E = \{$ Bereitschaft $\}$

Open Source: Der Latex-Code des DFA der Kaffeemaschine kann über GitHub unter der Academic Free License 3.0 bezogen werden.

3. Anwendung und Veranschaulichung

Der nachfolgende Teilbereich wird abschließend auf die Verwendung der einzelnen Klassen, sowie verschiedene unterstützende Veranschaulichungen eingehen. Dabei verwendet der DFA folgende reguläre Sprache:

$\mathscr{L}_{A} = \{w \in \{a, b\}^{∗} \textrm{ | } w $ enthält die Folge $bb$ jedoch nicht $ab \}$

In [2]:
# Bereitstellung der Basiskonfiguration des Deterministischen Endlichen Automaten
config = {
    "states": {"z1", "z2", "z3", "z4", "z5"},
    "alphabet": {"a", "b"},
    "transitions": dict(
        z1 = {'a':'z2', 'b':'z3'},
        z2 = {'a':'z2', 'b':'z2'},
        z3 = {'a':'z2', 'b':'z4'},
        z4 = {'a':'z5', 'b':'z4'},
        z5 = {'a':'z5', 'b':'z2'}
    ),
    "start_state": "z1",
    "end_states": {"z4", "z5"},
}

dfa = DFA(config)

3.1. Verarbeitung von Wortbeispielen durch den DFA mit Hilfe einer regulären Sprache

Nachfolgend soll der in der Basiskonfiguration definierte konkrete Automat mit Hilfe von Wortbeispielen getestet werden.

In [3]:
# Definition der zu testenden Wörter
words = [
    "bb",
    "bbbbb",
    "ab",
    "ababab",
    "bbababab"
]

# Ausgabe der durch den DFA akzeptierten und nicht akzeptierten Wörter.
for word in words:
    if(dfa.run(word)):
        print("Das Wort '{0}' wird durch den DFA akzeptiert.".format(word))
    else:
        print("Das Wort '{0}' wird durch den DFA nicht akzeptiert.".format(word))
Das Wort 'bb' wird durch den DFA akzeptiert.
Das Wort 'bbbbb' wird durch den DFA akzeptiert.
Das Wort 'ab' wird durch den DFA nicht akzeptiert.
Das Wort 'ababab' wird durch den DFA nicht akzeptiert.
Das Wort 'bbababab' wird durch den DFA nicht akzeptiert.

3.2. Ausgabe des DFA als zweidimensionale Grafik

Nachfolgend wird der DFA gemäß der obigen Basiskonfiguration als 2D-Plot ausgegeben.

In [4]:
# Ausgabe des DFA als 2D-Plot
dfa.plot()
Der Startzustand ist: z1
Die akzeptierten Endzustände sind: {'z5', 'z4'}

3.3. Vergleich von Verwaltungsstrukturen auf deren Effizienz

Nachfolgend werden die Verwaltungsstrukturen list und set auf ihre Effizienz geprüft.

In [5]:
# Definition eines Wortbeispiels
word = "ab"*20000

# Misst die Zeit mit einem Dictionary
time_with_dict = timeit("dfa.run(word)")

# Stellt den DFA entgültig auf Verwendung von Listen um.
dfa.use_list()

# Misst die Zeit mit einer Liste
time_with_list = timeit("dfa.run(word)")

print("Durchlauf mit Dictionary: {0}".format(time_with_dict))
print("Durchlauf mit Liste: {0}".format(time_with_list))
Durchlauf mit Dictionary: 25 loops, best of 3: 7.65 ms per loop
Durchlauf mit Liste: 25 loops, best of 3: 20.4 ms per loop

4. Literaturverzeichnis

[1] Patent US2017178003A1: Data pattern analysis using optimized deterministic finite automation. Veröffentlicht am 22. Juni 2017, Anmelder: SonicWall, Inc., Erfinder: Brady Justin, Michael; Dubrovsky, Aleksandr; Yanovsky, Boris; Yanovsky, Roman.
[2] Esparza, Javier (2017): Automata theory. An algorithmic approach. Online verfügbar unter http://www7.in.tum.de/um/courses/auto/ws1718/autoskript.pdf , zuletzt geprüft am 08.05.2020.
[3] Mark D. Flood and Oliver R. Goodenough: Contract as Automaton: The Computational Representation of Financial Agreements. Online verfügbar unter https://www.financialresearch.gov/working-papers/files/OFRwp-2015-04_Contract-as-Automaton-The-Computational-Representation-of-Financial-Agreements.pdf , zuletzt geprüft am 08.05.2020.
[4] Boockmeyer, Arne; Fischbeck, Philipp; Neubert, Stefan (2018): Informatik. 1. Auflage, 1., korrigierter Nachdruck. Bonn: Rheinwerk Verlag GmbH (Fit fürs Studium).
[5] N.N. (2020): timeit — Measure execution time of small code snippets — Python 3.8.3 documentation. Hg. v. Python Software Foundation. Online verfügbar unter https://docs.python.org/3.8/library/timeit.html, zuletzt aktualisiert am 19.05.2020, zuletzt geprüft am 19.05.2020.

5. Appendix

5.1. AUFGABENVERTEILUNG UNTER DEN TEAMMITGLIEDERN:

Implementierung eines allgemeinen Endlichen Automaten

Bearbeitung durch Stefan Kühnel und Hubert Fuchs

Prüfung verschiedener Datenstrukturen zur effizienten Verwaltung von Zustandsübergängen

Bearbeitung durch Hubert Fuchs

Definition einer plot-Methode zur Ausgabe des modellierten DFA

Bearbeitung durch Stefan Kühnel und Hubert Fuchs

Implementierung eines DFA mit einer bestimmten vorgegebenen Sprache

Bearbeitung durch Stefan Kühnel und Hubert Fuchs

Erstellung eines konkreten Automaten zur Modellierung einer Kaffeemaschine

Bearbeitung durch Stefan Kühnel

Copyright (c) 2020 Stefan Kühnel; Hubert Fuchs, Alle Rechte vorbehalten, soweit nicht ausdrücklich anders vermerkt.