Click here to load reader

Formale Sprachen Teil 2

  • View
    59

  • Download
    0

Embed Size (px)

DESCRIPTION

Formale Sprachen Teil 2. Klaus Becker 2006. Theorie formaler Sprachen. S  aAS S  bBS S  c Aa  aA Ab  bA Ac  ca Ba  aB Bb  bB Bc  cB. Komplexität von Grammatiken Automatenmodelle Zusammenhänge zwischen Grammatiken und Automaten. S  (T) T   T  (T). - PowerPoint PPT Presentation

Text of Formale Sprachen Teil 2

  • Formale SprachenTeil 2Klaus Becker 2006

  • Theorie formaler SprachenKomplexitt von GrammatikenAutomatenmodelleZusammenhnge zwischen Grammatiken und Automaten

    A [B B ] B (C C xD D )BS (T) T T (T)S aAS S bBS S c Aa aAAb bA Ac ca Ba aB Bb bB Bc cB

  • Beispiel: KlammersprachenKorrekt geklammerte Rechenausdrcke:(56 34) * 17 ((34 17) * (89 + 11)) (((45 6) * (67 / 5)) (6 * 5)) ... HTML-Dokument: ... Weiterbildungskurse Informatik Der Weiterbildungslehrgang Inf.... Der Lehrgang besteht ... Der Lehrgang schliesst ... XML-Dokument: grammar S a S A A a

  • Zielsetzung und VorgehensweiseZiel ist es, die Beschreibung von Klammersprachen mit Hilfe von Grammatiken und die Erkennung von Klammersprachen mit Hilfe von Automaten genauer zu untersuchen. Diese Untersuchungen fhren direkt zur Theorie ber formale Sprachen und Automaten. Um den Arbeits- und Schreibaufwand etwas zu verringern, werden die zu betrachtenden Sprachen zunchst strukturgetreu vereinfacht.

  • Teil 1Regulre Sprachen

  • Vereinfachtes HTMLInformelle Beschreibung:Ein vereinfachtes HTML-Dokument besteht aus einem Kopf mit Titelangabe und einem Rumpf mit Abschnitten. Es sind keine Umlaute erlaubt. Es sollen auch keine Tabellen, Links, Bilder etc. integriert werden. Der unten abgebildete HTML-Quelltext ist in diesem Sinne ein vereinfachtes HTML-Dokument. Weiterbildungskurs Informatik Der Weiterbildungslehrgang Informatik in Rheinland-Pfalz ist ein Ersatzstudium der Informatik fr Lehrerinnen und Lehrer, die bereits eine Lehrbefaehigung in einem naturwissenschaftlichen Fach haben. Der Lehrgang besteht aus sechs Wochenkursen, in denen jeweils typische Themen der Informatik bearbeitet werden. Der Lehrgang schliesst dann mit einer Pruefung zum Erwerb der Unterrichtserlaubnis fuer das Grundfach Informatik ab.

  • StrukturanalyseKlammerstruktur:Hier werden verschiedene Sorten von Klammern benutzt. Die verschiedenen Klammersorten knnen geschachtelt werden, aber nur in einer bestimmten Form. Der Rumpf-Teil hat z. B. die Struktur ............. Wir abstrahieren im Folgenden von der Darstellung der Klammern und betrachten Klammerausdrcke der Gestalt [(x)(x)...(x)]. Der Weiterbildungslehrgang ... in einem naturwissenschaftlichen Fach haben. Der Lehrgang besteht aus ... Themen der Informatik bearbeitet werden. Der Lehrgang schliesst ... fuer das Grundfach Informatik ab. Klammersprache K3:Das Alphabet von K3 ist die Zeichenmenge { [, ], (, ), x }. Zu K3 gehren alle Wrter ber dem Alphabet { [, ], (, ), x }, die mit [ beginnen, dann eine beliebige Anzahl (evtl. auch 0) von Ausdrcken der Gestalt (x) enthalten und mit ] enden.Bsp.: [], [(x)], [(x)(x)], [(x)(x)(x)], ...

  • AufgabeEntwickeln Sie eine (mehrere) Grammatik(en) zur Beschreibung der Klammersprache K3. Entwickeln Sie auch einen (mehrere) endliche Automaten zur Erkennung der Klammersprache K3.

  • Beschreibung und Erkennung von K3Klammersprache K3:Das Alphabet von K3 ist die Zeichenmenge { [, ], (, ), x }. Zu K3 gehren alle Wrter ber dem Alphabet { [, ], (, ), x }, die mit [ beginnen, dann eine beliebige Anzahl (evtl. auch 0) von Ausdrcken der Gestalt (x) enthalten und mit ] enden.Bsp.: [], [(x)], [(x)(x)], [(x)(x)(x)], ... [q0q1q2q3q4]x()Grammatik G1 fr K3:A [] A [B] B C B CB C (x)Grammatik G2 fr K3:A [B B ] B (C C xD D )BEndlicher Automat fr K3:

    K3GR1.jff

    K3GR2.jff

  • Erkennung von K3[q0q1q2q3q4]x()Grammatik G1 fr K3:A [] A [B] B C B CB C (x)Grammatik G2 fr K3:A [B B ] B (C C xD D )BEndlicher Automat fr K3:

    Beobachtung: Es fllt auf, dass die Grammatik G2 genau das Verhalten des endlichen Automaten A mit Hilfe von Produktionen nachbildet. ABK3GR1.jff

    K3GR2.jff

    CD

  • Aufgabeffnen Sie die Datei K3GR2.jff. Lassen Sie JFlap zu dieser Grammatik automatisch einen endlichen Automaten erzeugen: .Gehen Sie auch umgekehrt vor und lassen Sie sich von JFlap zum Automaten K3DA1.jff die entsprechende Grammatik erzeugen.

  • Aufgabeffnen Sie die Datei K3GR1.jff. Lassen Sie JFlap zu dieser Grammatik automatisch einen endlichen Automaten erzeugen: . Warum funktioniert das nicht?

  • Aufgabe1q0q1q20Wir betrachten die Sprache der Binrzahlen. Entwickeln Sie eine Grammatik zu dieser Sprache, die das Verhalten des gezeigten endlichen Automaten mit Hilfe von Produktionen nachbildet. Testen Sie Ihren Lsungsvorschlag mit Hilfe von JFlap.1 0

  • AufgabeWir betrachten die Sprache der Binrzahlen.Versuchen Sie jetzt, umgekehrt zu einer Grammatik fr diese Sprache einen entsprechenden endlichen Automaten zu entwickeln. Testen Sie Ihren Lsungsvorschlag mit Hilfe von JFlap. Was fllt hier auf?A 0 A 1 A 1B B 0B B 1B B 0 B 1

  • Rechtlineare GrammatikEine Produktion heit rechtslinear genau dann, wenn auf der linken Seite ein Nichtterminalsymbol steht und die rechte Seite folgende Gestalt hat: - ein Terminalsymbol gefolgt von einem Nichtterminalsymbolen oder - ein Terminalsymbol. alternativ: - ein Terminalsymbol gefolgt von einem Nichtterminalsymbolen oder - das leere Wort.Eine Grammatik heit rechtslinear / regulr genau dann, wenn alle Produktionen der Grammatik rechtslinear sind. Beispiele fr rechtslineare Produktionen:A 0A 1B B 0B 1 B 0BB 1BBeispiele fr rechtslineare Produktionen:A 0CC A 1B B 0DB 1D D B 0BB 1BBeispiele fr nicht-rechtslineare Produktionen:A 0B1A A1

  • quivalenzsatzSatz Zu jedem endlichen Automaten gibt es eine rechtslineare Grammatik, mit der die Sprache des Automaten erzeugt werden kann. Entsprechende Grammatik:A 1BA 0C B 0BB 1BB C 0DC 1D C D 0DD 1DEndlicher Automat:

    Idee: Zu jedem Zustandsbergang wird eine entsprechende Produktion gebildet. Zu jedem Endzustand wird eine entsprechende Produktion mit dem leeren Wort als rechter Seite hinzugefgt.1q0q1q201 01 0q31 0ABCD

  • Schwierigkeit bei der UmkehrungBei der Umwandlung einer rechtslinearen Grammatik in einen endlichen Automaten kann ein sog. nichtdeterministischer Automat entstehen. Von einem Zustand aus knnen bei gleicher Eingabe bergnge in verschiedene Zustnde erfolgen.Nichtdeterministischer Endlicher Automat:

    1q0q2q11 01 0Rechtslineare GrammatikA 1B A 0C A 1C C B 0BB 1B B 0DB 1DD q31 0ABNicht-determinismus

    CD

  • quivalenzsatzNichtdeterministischer Endlicher Automat:

    Satz Zu jeder rechtslinearen Grammatik gibt es einen nichtdeterministischen endlichen Automaten, der die von der Grammatik erzeugte Sprache erkennt. Idee: Man geht wie oben beschrieben vor. 1q0q2q11 01 0Rechtslineare GrammatikA 1B A 0C A 1C C B 0BB 1B B 0DB 1DD q31 0ABNicht-determinismus

    CD

  • Aufgabeffnen Sie die Datei BinZahlNA1.jff. Dieser nichtdeterministische Automat erkennt die Sprache der Binrzahlen. Lassen Sie diesen Automaten verschiedene Wrter verarbeiten (z. B. 1001). Machen Sie sich hieran die Arbeitsweise eines nichtdeterministischen Automaten klar.

  • Aufgabeffnen Sie die Datei BinZahlNA1.jff. Dieser nichtdeterministische Automat erkennt die Sprache der Binrzahlen. Lassen Sie JFlap diesen Automaten in einen deterministischen Automaten umwandeln: .

  • quivalenzsatzSatz Zu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Idee: Jede Menge von Zustnden des NEA ergibt einen Zustand des DEA. Nicht bentigte Zustnde des DEA werden weggelassen.

  • quivalenzsatzSatz Zu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Bemerkung:Da jeder deterministische Automat auch ein nichtdeterministischer Automat ist, gilt trivialerweise auch die Umkehrung: Zu jedem deterministischen Automaten gibt es einen nichtdeterministischen Automaten, der dieselbe Sprache erkennt.Folgerung:Deterministische und nichtdeterministische Automaten sind gleich mchtige Sprachverarbeitungsmodelle / erkennen dieselben Sprachen.

  • Aufgabeffnen Sie die Datei BinZahlDA2.jff. Dieser deterministische Automat erkennt die Sprache der Binrzahlen. Lassen Sie JFlap diesen Automaten in einen regulren Ausdruck umwandeln: . Exportieren Sie anschlieend diesen regulren Ausdruck und lassen Sie ihn wieder in einen endlichen Automaten umwandeln. Was zeigen diese Experimente?

  • quivalenzsatzSatz (Kleene) Jede durch einen endlichen Automaten erkennbare Sprache kann durch einen regulren Ausdruck beschrieben werden. Jede durch einen regulren Ausdruck beschreibbare Sprache kann durch einen endlichen Automaten erkannt werden.

  • Regulre SprachenEine Sprache heit regulr genau dann, wenn sie durch einen regulren Ausdruck dargestellt werden kann.Bemerkung:Eine Sprache ist regulr genau dann, wenn sie- durch einen regulren Ausdruck dargestellt werden kann /- von einem deterministischen endlichen Automaten erkannt werden kann /- von einem nichtdeterministischen endl. Automaten erkannt werden kann /- von einer rechtslinearen Grammatik erzeugt werden kann.Die genannten Sprachbeschreibungs- bzw. Sprachverarbeitungskonzepte sind demnach alle gleich mchtig.

  • Teil 2Kontextfreie Sprachen

  • RechenausdrckeRechenausdrcke knnen Klammern enthalten, mit denen die Reihenfolge von Berechnungen genau festgelegt wird.Beispiele fr korrekt geklammerte Rechenausdrcke:((56 34) * 17) ((34 17) * (89 + 11)) ... Beispiele fr inkorrekt geklammerte Rechenausdrcke:)13 + 12) * 4 ((25 16) * 7 ...

  • Vereinfachte RechenausdrckeInformelle Beschreibung:Wir betrachten nur Rechenterme, die vollstndig geklammert sind. Jede Rechenoperation muss umklammert werden wie z. B. bei (12+3). Eine Rechenoperation bezieht sich auf Zahlen oder Rechenterme wie z. B. bei ((1