Miniprojekt - Automatensimulator

Zielsetzung

Bei der Entwicklung eines Automatensimulators orientieren wir uns an dem Software-Werkzeug JFlap.

Ziel ist es, einen von JFlap erzeugten XML-Quelltext zur Beschreibung eines endlichen Automaten mit Hilfe eines selbst entwickelten Automatensimulators zu verarbeiten. Dieser Simulator muss also XML-Quelltexte wie den folgenden verarbeiten können.

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!--Created with JFLAP 6.4.-->
<structure>
	<type>fa</type>
	<automaton>
		<!--The list of states.-->
		<state id="0" name="q0">
			<x>60.0</x>
			<y>59.0</y>
			<initial/>
		</state>
		<state id="1" name="q1">
			<x>147.0</x>
			<y>59.0</y>
		</state>
		...
		<state id="5" name="q5">
			<x>510.0</x>
			<y>59.0</y>
			<final/>
		</state>
		<!--The list of transitions.-->
		<transition>
			<from>4</from>
			<to>5</to>
			<read>b</read>
		</transition>
		...
		<transition>
			<from>1</from>
			<to>2</to>
			<read>@</read>
		</transition>
	</automaton>
</structure>

email.jff

Entwicklung eines Automatensimulators

Der folgende Python-Quelltext zeigt einen Ausschnitt aus einer Implementierung eines Automatensimulators.

from xml.dom.minidom import *

# Anfangszustand
def anfangszustand(baum):
    z = None
    k_initial_liste = baum.getElementsByTagName("initial")
    if k_initial_liste != []:
        k_state = k_initial_liste[0].parentNode
        z = k_state.getAttribute("id")
    return z

# nächster Zustand
def naechsterzustand(baum, zustand, eingabe):
    pass

# Endzustand
def endzustand(baum, zustand):
    pass

# Einlesen des XML-Quelltextes
f_xml = open("email.jff", "r")
xml_quelltext = f_xml.read()

# Initialisierung des DOM-Baums
dombaum = parseString(xml_quelltext)
wurzel = dombaum.documentElement

# Test
z = anfangszustand(wurzel)
print(z)

Aufgabe 1

Analysiere zunächst den gezeigten Python-Quelltext. Was leistet die Funktion anfangszustand? Benutze die Datei "email.jff" zum Testen.

Aufgabe 2

Ergänze die Implementierung der beiden Funktionen naechsterzustand und endzustand. Teste anschließend die Funktionen wie folgt:

...

z = anfangszustand(wurzel)
print(z)
wort = "bbb@b.bb"
for w in wort:
    z = naechsterzustand(wurzel, z, w)
    print(z)
if endzustand(wurzel, z):
    print("akzeptiert")
else:
    print("nicht akzeptiert")

Objektorientierte Realisierung

Zur objektorientierten Realisierung eines Automatensimulators wird die Klasse Automat modelliert.

Der folgende Python-Quelltext zeigt einen Ausschnitt aus einer Implementierung der Klasse Automat sowie einen einfachen Test dieser Klasse.

class Automat(object):
    def __init__(self, quelltext):
        self.quelltext = quelltext
        self.dombaum = parseString(self.quelltext)
        self.wurzel = self.dombaum.documentElement
        self.zustand = None

    def anfangszustand(self):
        k_initial_liste = self.wurzel.getElementsByTagName("initial")
        if k_initial_liste != []:
            k_state = k_initial_liste[0].parentNode
            self.zustand = k_state.getAttribute("name")

    def naechsterzustand(self, eingabe):
        pass

    def endzustand(self):
        pass

    def getZustand(self):
        return self.zustand

# Test
f_xml = open("email.jff", "r")
xml_quelltext = f_xml.read()

automat = Automat(xml_quelltext)

automat.anfangszustand()
print(automat.getZustand())
automat.naechsterzustand("b")

Aufgabe 3

Ergänze die Implementierung der beiden Methoden naechsterzustand und endzustand. Teste anschließend die Methoden.

Aufgabe 4

Entwickle eine Klasse Simulator. Objekte dieser Klasse sollen ein eingegebenes Wort mit Hilfe eines Automaten abarbeiten und entscheiden, ob das Wort vom Automaten akzeptiert wird.