Bibliograph. Daten | Baumann, Thomas: Quantorenalternierung und reguläre Sprachen. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2775 (2008). 37 Seiten, deutsch.
|
CR-Klassif. | F.4.3 (Formal Languages)
|
Keywords | formale Sprachen, reguläre Ausdruecke, dot-depth Hierarchie |
Kurzfassung | Seit den 1960er Jahren befindet sich die Dot-Depth Hierarchie von Brzozowski und Cohen im Zentrum der Erforschung sternfreier regulärer Sprachen. Sie bildet in diesen eine strikte Hierarchie, deren Vereinigung gerade die sternfreien Sprachen ergibt und die bis zum heutigen Tage trotz einiger erstaunlicher Teilresultate nur auf den untersten Ebenen vollständig verstanden wird.
Die vorliegende Arbeit befasst sich mit einem Resultat von Straubing aus dem Jahre 1988, das die Entscheidbarkeit der zweiten Stufe dieser Hierarchie für Sprachen mit maximal zwei Erzeugern nachweist. Insbesondere wird dieses Resultat im Licht neuerer Erkenntnisse der algebraischen Sprachentheorie betrachtet und eine notwendige Bedingung für das Enthaltensein in einer bestimmten Klasse von Monoiden erarbeitet. Abschließend wird diese verwendet um einen neuen Gegenbeweis einer Vermutung, über die Struktur der zweiten Stufe von Brzozowskis Hierarchie, aus dem Jahre 2001 zu widerlegen.
|
Volltext und andere Links | PDF (328080 Bytes) PostScript (572538 Bytes) Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich |
Copyright | Thomas Baumann |
Kontakt | tombau@t-online.de |
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
Betreuer | Kufleitner, Manfred |
Eingabedatum | 13. März 2009 |
---|