Transformationen von Darstellungsarten regulärer Sprachen

Publikation: ArbeitspapierArbeits- und Diskussionspapier

Abstract

Dieser technische Bericht behandelt Transformationsverfahren zwischen einigen ausgewählten Darstellungsarten regulärer Sprachen. Reguläre Sprachen können durch Grammatiken, durch endliche Automaten und durch reguläre Ausdrücke dargestellt werden. Bei den Grammatiken kann man zwischen regulären, umgekehrt-regulären, rechts-linearen und links-linearen Gram¬matiken unterscheiden, wobei die linearen Formen im wesentlichen Erweiterungen der einfach-regulären Formen repräsentieren. Bei den endlichen Automaten kann man zwischen deterministischen und nicht-deterministischen endlichen Automaten unterscheiden. (Das für Transformationen schwierige Gebiet der regulären Ausdrücke bleibt hier ausgeklammert — das bleibt wohl einer speziellen Notiz vorbehalten.) Die hier behandelten Probleme sind zwar einfach, aber doch so geartet, dass — wie die Erfahrung aus den Übungen zu Formale Sprachen zeigt — immer wieder kleine Fehler passieren können. Eine ausführliche Schilderung der Transformationsidee, eine verbale Beschreibung der Transformation sowie die Angabe detaillierter Algorithmen (in einem Modula-2-artigen Pseudocode) soll diese Schwierigkeiten für die Zukunft aus der Welt schaffen.
Titel in ÜbersetzungTransformationen von Darstellungsarten regulärer Sprachen
OriginalspracheDeutsch
HerausgeberJohannes Kepler Universität Linz
Seitenumfang14
PublikationsstatusVeröffentlicht - 1991

Zitieren