Material OOP Grundlagen Delphi Software-Technik Bonsai Digitaltechnik Ereignisse Grafik UML Netze Fischertechnik Tipps Werkzeuge Literatur Automaten Sprachen Datenbanken XML Prolog Berechenbarkeit
Pfad: Startseite / Fächer / Informatik / Material
Autor: mk
27.06.2004 17:03
5149
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.