Transformationen von Darstellungsarten regulärer Sprachen

Research output: Working paperWorking paper/discussion paper

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.
Translated title of the contributionTransformationen von Darstellungsarten regulärer Sprachen
Original languageGerman
PublisherJohannes Kepler Universität Linz
Number of pages14
Publication statusPublished - 1991

Cite this