Home >Documents >Formale Sprachen St¤dtisches Gymnasium Beverungen Friedel Berlage

Formale Sprachen St¤dtisches Gymnasium Beverungen Friedel Berlage

Date post:06-Apr-2015
Category:
View:108 times
Download:4 times
Share this document with a friend
Transcript:
  • Folie 1
  • Formale Sprachen Stdtisches Gymnasium Beverungen Friedel Berlage
  • Folie 2
  • natrliche knstliche Sprachen natrliche Sprachen dienen der Kommunikation zwischen Menschen sind natrlich gewachsen, sind universal sind daher oft mehrdeutig formale Sprachen dienen bestimmten speziellen Zwecken Formelsprachen (Mathematik, Chemie,....) sind prgnant und eindeutig (oder sollten es sein)
  • Folie 3
  • Sprachkategorien Syntax Beschreibt den formalen Aufbau der Worte und Stze wie schreibe ich etwas Semantik Bestimmt die inhaltliche Bedeutung was bedeutet dieser Satz Pragmatik Untersucht die Verwendung sprachlicher Gebilde in Handlungssituationen wann gebrauche ich welchen Ausdruck
  • Folie 4
  • Formale Sprachen in der Informatik Teilgebiet der theoretischen Informatik Einteilung der formalen Sprachen in Klassen Chomsky-Hierarchie Typ 0 bis Typ 3 Sprachen Bedeutung beim bersetzen in Maschinensprache Compiler Interpreter
  • Folie 5
  • Compiler - Interpreter Compiler bersetzt aus Hochsprache in Maschinensprache effizient muss vor dem Ablauf des Programms gemacht werden fr jeden Prozessor ein anderer Compiler Interpreter arbeitet unmittelbar mit der Hochsprache lsst das eigentliche Programm ablaufen langsam unabhngig vom Prozessor
  • Folie 6
  • bersetzungsphasen Analyse lexikalische Analyse Scanner zerlegt Eingabestrom in einzelne Symbole (Token) syntaktische Analyse Automat zum Erkennender Struktur des Programms erkennt Schleifen, Methodenaufrufe und alle anderen Sprachelemente erkennt auch syntaktische Fehler (Rechtschreibfehler) Synthese Erzeugt neues Programm in der Zielsprache
  • Folie 7
  • Phasen beim Compilieren
  • Folie 8
  • Automaten-Grammatiken Automaten erkennen Worte der Sprache Grammatiken erzeugen Worte der Sprache
  • Folie 9
  • endlicher Automat (Akzeptor) 5 Tupel {,Z, z0,E, }gegeben durch: Eingabemenge Zustandsmenge Z Anfangszustand z0 genau ein Anfangszustand z0 Endzustnde E mehrere Endzustnde bergangsfunktion Ordnet jedem Paar {z,x} einen neuen Zustand zu
  • Folie 10
  • Beispiel eines endlichen Automaten Welche Worte akzeptiert dieser Automat? bergangstabelle Zustandsdiagramm Er soll alle Worte erkennen, in denen man vorkommt. Tut er das?
  • Folie 11
  • Nichtdeterministischer Automat bergangstabelle keine Funktion sondern Relation es kann mehr als einen Nachfolgezustand geben Beispiel
  • Folie 12
  • Potenzmengenkonstruktion Zu jedem nichtdeterministischen Automaten existiert ein quivalenter deterministischer Beide Arten sind also gleich mchtig, akzeptieren die gleichen Sprachen Die Anzahl der Zustnde kann dabei aber explodieren (Potenzmenge (2 n ))
  • Folie 13
  • Konstruktionsbeispiel Nichtdeterministischer Automat Deterministischer Automat Fasse die erreichten Zustnde als neuen Zustand auf ab {s0}{s0,s1}{s0} {s0,s1} {s0,s2} {s0,s1,s3} {s0} {s0,s1,s3} {s0,s1}{s0,s2} ' s0' s1' s2' s3'
  • Folie 14
  • Grammatiken Erzeugen Worte einer Sprache Legen die Syntax (Regeln) einer Sprache fest Formal ist eine Grammatik ein 4-Tupel G={V,, P, S} V: Nichtterminal-Symbole : Terminalsymbole P: Menge der Produktionen A S: Startsymbol blicherweise werden Nichtterminale gro und Terminale klein geschrieben
  • Folie 15
  • Regulre Grammatik Grammatik, die die von endlichen Automaten erkannten Sprachen erzeugt die Sprachen heien regulre Sprachen die Worte der Sprache auch regulre Ausdrcke die Produktionsregeln sind stark eingeschrnkt (Typ 3 Sprache) fr alle Produktionen gilt die Regel links darf nur ein Nichtterminal und rechts nur Nichtterminal- Terminal(linksregulr) bzw. Terminal- Nichtterminal (rechtsregulr) stehen (eingeschrnkt kontextfrei)
  • Folie 16
  • Beispiel einer regulren Grammatik G={V,, P, S} (rechtslineare Grammatik) V={S,A,B} ; ={a,b} P={SaB; SbA; Aa; AbB; BaB; Bb} Einige Ableitungen SaB Bb {a,b} SbA AbB BaB Bb {bbab} Erzeugte regulre Sprache?
  • Folie 17
  • Welche regulre Sprache? P={SaB; SbA; Aa; AbB; BaB; Bb} welches sind die krzesten Worte der Sprache? wie enden die meisten Wrter? welche Worte enden auf a? {bb} L ? welches ist das lngste Wort? L={ba}u{a,bb}{a} * {b} das einzelne Wort {ba} oder ein Wort, das mit a oder bb anfngt, dann kommen beliebig viele a und am Schluss ein b
  • Folie 18
  • Grammatik Automat P={SaB; SbA; Aa; AbB; BaB; Bb} Nichtterminale werden Zustnde Terminale werden Eingabesymbole Startsymbol wird Startzustand Produktionen werden bergangsfunktion Produktionen ohne Nichtterminale werden Endzustnde
  • Folie 19
  • Regulre Sprache kontextfreie Spr. regulre Grammatiken sind in ihrer Ausdrucksstrke zu begrenzt, um als Programmiersprachen dienen zu knnen aufgrund ihrer endlich vielen Zustnde knnen endliche Automaten potentiell-unendliche Strukturen nicht erkennen. so kann die Sprache L={a n b n } fr beliebig groe n nicht erkannt, bzw. erzeugt werden damit knnen regulre Grammatiken nicht einmal gewhnliche mathematische Terme erzeugen fr solche Strukturen werden Maschinen mit einem Stack bentigt.
  • Folie 20
  • Kellerautomat (PushDownAutomaton) endlicher Automat, der um einen Stack(Keller) erweitert wurde Ausdruckskrftig genug, um die syntaktische Analyse von Programmiersprachen zu leisten deterministische Kellerautomaten (DPDA) sind schwcher als nichtdeterministische (NPDA) NPDAs erkennen Worte (Programme) die von kontextfreien Grammatiken generiert werden i.A. reichen DPDAs, zur syntaktischen Analyse aus L={a n b n a m }u{a m b n a n }wird von NPDAs erkannt, aber nicht von DPDAs
  • Folie 21
  • Kellerautomat (PushDownAutomaton)
  • Folie 22
  • kontextfreie Grammatiken wichtigste Beschreibungsart fr die Syntax von Programmiersprachen ( Ausdruck, Kontrollstrukt.) erzeugen die kontextfreien Sprachen (Typ-2) gleichwertige Beschreibungsarten: Backus-Naur-Formen Syntaxdiagramme
  • Folie 23
  • Produktionen kontextfr. Grammatiken Alle Regeln haben die Form: N als linke Regelseite sind nur einzelne Nichtterminale erlaubt so kann ein Nichtterminalsymbol unabhngig von seiner Umgebung (kontextfrei) ersetzt werden Beispiel: G={V,, P, S} mit: V={S} ; ={a,b} ; P={S , S aSb} G erzeugt die kontextfreie Sprache L={a n b n }, die keine regulre Sprache ist kontextfreie Grammatiken knnen mehrdeutig sein x+y*z (x+y) *z oder x+(y*z)
  • Folie 24
  • kontextsensitive Sprache (Typ-1) formale Sprache, die von einer kontextsensitiven Grammatik erzeugt, und von linear beschrnkten Turingmaschinen erkannt werden kann Produktionen der Grammatik haben die Form: N das Nichtterminal N kann im Kontext .. durch ersetzt werden bei der Turingmaschine kann die Lnge des Arbeitsbandes durch die Lnge des Eingabewortes beschrnkt sein sie sind mchtiger als kontextfreie Sprachen z.B. ist die Sprache L = {a n b n c n } nicht kontextfrei
  • Folie 25
  • Allgemeine Sprachen (Typ-0) Sprachen, die von Grammatiken ohne Einschrnkungen erzeugt werden knnen sie werden von Turingmaschinen (und damit auch von Computern) erkannt Chomsky-Hierarchie: Ent : Entscheidbare Spr CS : Kontextsensitiv CF : Kontextfrei Lin : Lineare Grammat. DPDA: det.Kellerautomat RL : regulre Sprache TM: Turingmaschine Auf: aufzhlbare Spr. NLBA: nichtdeterminist. lin. beschr. Automat NPDA: nichtdeterminist. push-down-automaton RL : rechtslinear LL : linkslinear EA : endlicher Automat

Click here to load reader

Embed Size (px)
Recommended