Sprachen	Material Lehrgang Darstellung reguläre Sprachen kontextfreie Sprachen Chomsky-Hierarchie xml abc Compiler Pfad: Startseite / Fächer / Informatik / Theorie / Sprachen
Autor: mk 13.06.2008 16:09:05 145	Formale Sprachen

Systematische Entwicklung einer Grammatik aus einem regulären Ausdruck

Gegeben sei der reguläre Ausdruck (a+b)*aba. Es soll zunächst gemäß dem Automaten-Baukasten ein Automat konstruiert werden, der (a+b)*aba erkennt.

Anschließend wird der Automat von JFLAP in eine rechtslineare Grammatik konvertiert. Diese Grammatik wird dann zum Schluss im Gold-Parser eingegeben und getestet.

Konstruktion des Automaten zu a+b

NFA

DFA

Konstruktion des Automaten zu (a+b)*

NFA	DFA abstern.jff

Konstruktion des Automaten zu aba

NFA

DFA

Konstruktion des Automaten zu (a+b)*aba

NFA	DFA re2a2.jff

Konvertierung des Automaten in eine Grammatik

Eingabe und Test der Grammatik im Gold-Parser

re2gr2.grm

Aufgabe

Entwickle in analoger Weise Grammatiken, die a(a+b)*abb und a(a+b)*aa(a+b)* erkennen.

Beachte, dass ein Automat, der a(a+b)* erkennt, ein gemeinsames Zwischenresultat ist.

Teste die Grammatiken, protokolliere die Testdaten.

lokal