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>

Entwicklung eines Automatensimulators

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

from xml.dom.minidom import *
<h1>Anfangszustand</h1>
<p>def anfangszustand(baum):<br />
z = None<br />
k_initial_liste = baum.getElementsByTagName("initial")<br />
if k_initial_liste != []:<br />
k_state = k_initial_liste[0].parentNode<br />
z = k_state.getAttribute("id")<br />
return z</p>
<h1>nächster Zustand</h1>
<p>def naechsterzustand(baum, zustand, eingabe):<br />
pass</p>
<h1>Endzustand</h1>
<p>def endzustand(baum, zustand):<br />
pass</p>
<h1>Einlesen des XML-Quelltextes</h1>
<p>f_xml = open("email.jff", "r")<br />
xml_quelltext = f_xml.read()</p>
<h1>Initialisierung des DOM-Baums</h1>
<p>dombaum = parseString(xml_quelltext)<br />
wurzel = dombaum.documentElement</p>
<h1>Test</h1>
<p>z = anfangszustand(wurzel)<br />
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:

...
<p>z = anfangszustand(wurzel)<br />
print(z)<br />
wort = "bbb@b.bb"<br />
for w in wort:<br />
z = naechsterzustand(wurzel, z, w)<br />
print(z)<br />
if endzustand(wurzel, z):<br />
print("akzeptiert")<br />
else:<br />
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
<pre><code>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.