KIT | KIT-Bibliothek | Impressum | Datenschutz

100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 3: Minimierung endlicher Automaten

Schmeck, Hartmut

Abstract:

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit der Minimierung deterministischer endlicher Automaten ohne Ausgabe (DEA). Dabei wird untersucht, ob ein DEA ?verkleinert? werden kann, ohne dass sich die von ihm erkannte Sprache ändert. Die Aufzeichnung stellt einen Algorithmus vor, der auf dem Satz von Myhill-Nerode beruht und zu einem DEA einen äquivalenten DEA mit minimaler Zustandszahl ausgibt. Dabei werden zuerst alle nicht erreichbaren Zustände entfernt und dann durch Markierung aller Zustandspaare, die zueinander nicht äquivalent sind, redundante Zustände erkannt und entfernt. Der Algorithmus wird formal spezifiziert und anhand von Beispielen erläutert.


Zugehörige Institution(en) am KIT KIT-Bibliothek (BIB)
Publikationstyp Audio & Video
Publikationsdatum 31.10.2013
Erstellungsdatum 31.10.2013
Sprache Deutsch
DOI 10.5445/DIVA/2013-744
Identifikator KITopen-ID: 1000111721
Lizenz KITopen-Lizenz
Serie 100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik
Folge 20
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page