Übung Basismodul Computerlinguistik

Hausaufgabe 03

04.11.2021

Abgabe als .py-Datei (bei mehreren Dateien als .zip komprimiert) an e.nie@campus.lmu.de bis 11.11.2021 (Keine Pflicht).

In dieser Woche wird ein Deterministischer Endlicher Automat als Klasse in Python implementiert und dann mithilfe der Python-Bibliothek graphviz visualisiert.

Aufgabe 1

In dieser Aufgabe soll ein Deterministischer Endlicher Automat implementiert werden.

Für diese Aufgabe werden die Datenstrukturen der Parameter für den Konstruktur (=__init__) der Klasse wie folgt definiert:

• $\Sigma$ ist ein set von Symbolen.
• Q ist ein set von Zahlen (den Namen der Zustände)
• s ist ein Element aus Q
• F ist ein set, eine Teilmenge von Q
• $\delta$ ist ein set mit tuple-Objekten der Länge 3, mit der Form (q_from, label, q_to)

a) Denke dir Beispieldaten nach dem obrigen Schema aus, die später benutzt werden, um den Automaten zu initialisieren. Definiere dazu eine Variable für jedes der Symbole, und weise einen passenden, selbstgewälten Wert zu. Acht darauf, dass ein deterministischer, endlicher Automat entsteht.

*Tipp: Unter Umständen hilft es, einen einfachen Automaten zu zeichnen, den du dann umsetzt. Dann wird es später leichter, zu prüfen, ob deine Klasse funktioniert.

b) Schreibe eine neue Klasse DEA, deren __init__-Funktion die obrigen 5 Elemente annimmt.

c) Immer über das set zu iterieren ist ineffizient. Der Lookup mithilfe eines dict ist viel schneller. Ändere deshalb die __init__-Funktion so, dass die Übergangsfunktion $\delta$ als Dictionary gespeichert wird. Die key-Einträge sollen dabei Kombinationen von Zustand und Label sein, die value-Einträge das Ziel des Übergangs. Die Form des key-value-Paares sieht aus wie (q_from, label) : q_to.

d) Schreibe eine Methode transition(self, q_from, label), die einen Zustand oder None zurückliefert, je nachdem, ob es von q_from einen Übergang mit Label label gibt. Wenn es den Übergang gibt, dann wird der Zielzustand q_to zurückgegeben. Benutze für diese Methode das schnelle dict aus Aufgabe c).

e) Füge eine Methode accept(self, sequence) hinzu, die eine Sequenz von Eingabesymbolen annimmt, und die boolschen Werte True oder False zurückliefert, je nachdem, ob dieser Automat die Eingabe akzeptiert. Benutze dazu die Funkion transition aus der letzten Aufgabe.

Achtung: Die folgenden Szenarien muss man beachten:

• Es kann sein, dass die Eingabe ein Symbol enthält, das nicht in $\Sigma$ ist.
• Es kann sein, dass die Eingabe leer ist.
• Es kann sein, dass es von einem Zustand keinen passenden Übergang gibt. Solche Eingaben werden vom Automat nicht akzeptiert.

f) Teste deine accept-Methode mit einigen Eingaben.

Aufgabe 2

Zeit, den Automat zu zeichnen! Wir benutzen dazu die Bibliothek graphviz. Um es in Python zu benutzen, brauchsr du sowohl die Python-API (https://pypi.org/project/graphviz/) als auch das Rendering (https://www.graphviz.org/download/).

a) Stelle sicher, dass eine Instanz der DEA-Klasse folgende Attribute hat:

• sigma liefert ein set von Symbolen
• states liefert ein set von Zustandsnamen (Zahlen)
• initial_state liefert den Startzustand
• final_states liefert ein set von Finalzuständen
• delta liefert ein set von 3-Tupeln der Form (q_from, label, q_to)

Hinweis: Um delta als ein set von 3-Tupeln abzurufen, wird es dazu @property empfohlen, den Decorator @property zu verwenden.

Beispiel:

class DEA:
    def __init__(self, sigma, states, delta, initial_state, final_states): # ...
        self.sigma = sigma
        self.states = states
        self._delta = {(q_from, label) : q_to for q_from, label, q_to in delta}# Verwende dict, um die Übergangsfunktion zu speichern.
        self.initial_state = initial_state
        self.final_states = final_states
    
    @property
    def delta(self):
        # liefere delta als set aus self._delta
        return {(q_from, label, q_to) for (q_from, label), q_to in self._delta.items()}  # set von 3-Tupeln
    
    def transition(self, q_from, label):
        try:
            return self._delta[(q_from, label)]
        except KeyError:
            return None
    
    # oder
    '''
    def transition(self, q_from, label):
        return self._delta.get((q_from, label))
    '''
    
    def accept(self, word):
        q = self.initial_state
        for char in word:
            q = self.transition(q, char)
            if q is None:
                return False
        return q in self.final_states    

b) Ersetze das TODO durch eine Instanz der DEA-Klasse, um deinen Automat an die Funktion zu übergeben und ihn zu zeichnen.

import graphviz

def draw_automaton(aut):
    
    g = graphviz.Digraph('Automaton')
    
    for state in aut.states:
        if state in aut.final_states:
            g.attr('node', style='bold')
        if state == aut.initial_state:
            g.node(str(state), label='-> ' + str(state))
        else:
            g.node(str(state))
        g.attr('node', style='solid')
    
    for x, label, z in aut.delta:
        g.edge(str(x), str(z), label=' ' + label + ' ')
    
    return g

sigma = {'a', 'b'}
states = {1, 2, 3, 4, 5}
delta = {
    (1, 'a', 1), (1, 'b' ,2),
    (2, 'a', 3), (2, 'b' ,2),
    (3, 'a', 5), (3, 'b' ,4),
    (4, 'a', 1), (4, 'b' ,5),
    (5, 'a', 5), (5, 'b' ,5)
}
initial_state = 1
final_states = {4}

aut = DEA(sigma, states, delta, initial_state, final_states)

test_data = [
    ('', False),
    ('abc', False),
    ('aab', False),
    ('bbab', True),
    ('baab', False),
    ('abababab', True)
]

for word, should_accept in test_data:
    if aut.accept(word) != should_accept:
        print(f"'{word}' was accpeted:{not should_accept}\nExpected was: {should_accept}")

# Aufruf durch
g = draw_automaton(aut)
g