Formale Sprachen
Städtisches Gymnasium BeverungenFriedel Berlage
natürliche – künstliche Sprachen
natürliche Sprachen
dienen der Kommunikation zwischen Menschen
sind natürlich gewachsen, sind universal
sind daher oft mehrdeutig
formale Sprachen
dienen bestimmten speziellen Zwecken
Formelsprachen (Mathematik, Chemie, ....)
sind prägnant und eindeutig (oder sollten es sein)
SprachkategorienSyntax
Beschreibt den formalen Aufbau der Worte und Sätze
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
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
Compiler - Interpreter
Compiler
Übersetzt aus Hochsprache in Maschinensprache
effizient
muss vor dem Ablauf des Programms gemacht werden
für jeden Prozessor ein anderer Compiler
Interpreter
arbeitet unmittelbar mit der Hochsprache
lässt das eigentliche Programm ablaufen
langsam
unabhängig vom Prozessor
Übersetzungsphasen
Analyse
lexikalische Analyse
Scannerzerlegt Eingabestrom in einzelne Symbole (Token)
syntaktische Analyse
Automat zum Erkennender Struktur des Programmserkennt Schleifen, Methodenaufrufe und alle anderen Sprachelemente
erkennt auch syntaktische Fehler (Rechtschreibfehler)
Synthese
Erzeugt neues Programm in der Zielsprache
Phasen beim Compilieren
Automaten-Grammatiken
Automaten
erkennen Worte der Sprache
Grammatiken
erzeugen Worte der Sprache
endlicher Automat (Akzeptor)
5 Tupel {∑,Z, z0,E,δ }gegeben durch:
Eingabemenge ∑
Zustandsmenge Z
Anfangszustand z0
genau ein Anfangszustand z0
Endzustände E
mehrere Endzustände
Übergangsfunktion δ
Ordnet jedem Paar {z,x} einen neuen Zustand zu
Beispiel eines endlichen Automaten
Welche Worte akzeptiert dieser Automat?
ÜbergangstabelleZustandsdiagramm
Er soll alle Worte erkennen, in denen „man“ vorkommt.Tut er das?
Nichtdeterministischer Automat
Übergangstabelle keine Funktion sondern Relation
es kann mehr als einen Nachfolgezustand geben
Beispiel
δ a bs0 {s0,s1} {s0}s1 {s2}s2 {s3}s3
Potenzmengenkonstruktion
Zu jedem nichtdeterministischen Automaten existiert ein äquivalenter deterministischer
Beide Arten sind also gleich mächtig, akzeptieren die gleichen Sprachen
Die Anzahl der Zustände kann dabei aber explodieren (Potenzmenge (2n ))
KonstruktionsbeispielNichtdeterministischer Automat
δ a bs0 {s0,s1} {s0}s1 {s2}s2 {s3}s3
Deterministischer Automat
Fasse die erreichten Zustände als neuen Zustand auf
δ a b
{s0} {s0,s1} {s0}
{s0,s1} {s0,s1} {s0,s2}
{s0,s2} {s0,s1,s3} {s0}
{s0,s1,s3} {s0,s1} {s0,s2}
δ'
s0'
s1'
s2'
s3'
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
Reguläre Grammatik
Grammatik, die die von endlichen Automaten erkannten Sprachen erzeugt
die Sprachen heißen reguläre Sprachen
die Worte der Sprache auch reguläre Ausdrücke
die Produktionsregeln sind stark eingeschränkt (Typ 3 Sprache)
für alle Produktionen gilt die Regellinks darf nur ein Nichtterminal und rechts nur Nichtterminal-Terminal(linksregulär) bzw. Terminal- Nichtterminal (rechtsregulär) stehen (eingeschränkt kontextfrei)
Beispiel einer regulären Grammatik
G={V, ∑, P, S} (rechtslineare Grammatik)
V={S,A,B} ; ∑={a,b}
P={S→aB; S→bA; A→a; A→bB; B→aB; B→b}
Einige Ableitungen
S→aB
B→b ► {a,b}
S→bA
A→bBB→aB
B→b ► {bbab}
Erzeugte reguläre Sprache?
Welche reguläre Sprache?
P={S→aB; S→bA; A→a; A→bB; B→aB; B→b}
welches sind die kürzesten Worte der Sprache?
wie enden die meisten Wörter?
welche Worte enden auf a?
{bb} ε L ?
welches ist das längste Wort?
L={ba}u{a,bb}∙{a}*∙{b}
das einzelne Wort {ba} oder
ein Wort, das mit a oder bb anfängt, dann kommen beliebig viele a und am Schluss ein b
Grammatik ↔ Automat
P={S→aB; S→bA; A→a; A→bB; B→aB; B→b}
Nichtterminale werden Zustände
Terminale werden Eingabesymbole
Startsymbol wird Startzustand
Produktionen werden Übergangsfunktion
Produktionen ohne Nichtterminale werden Endzustände
Reguläre Sprache →kontextfreie Spr.
reguläre Grammatiken sind in ihrer Ausdrucksstärke zu begrenzt, um als Programmiersprachen dienen zu können
aufgrund ihrer endlich vielen Zustände können endliche Automaten potentiell-unendliche Strukturen nicht erkennen.
so kann die Sprache L={anbn} für beliebig große n nicht erkannt, bzw. erzeugt werden
damit können reguläre Grammatiken nicht einmal gewöhnliche mathematische Terme erzeugen
für solche Strukturen werden Maschinen mit einem Stack benötigt.
Kellerautomat (PushDownAutomaton)
endlicher Automat, der um einen Stack(Keller) erweitert wurde
Ausdruckskräftig genug, um die syntaktische Analyse von Programmiersprachen zu leisten
deterministische Kellerautomaten (DPDA) sind schwächer als nichtdeterministische (NPDA)
NPDAs erkennen Worte (Programme) die von kontextfreien Grammatiken generiert werden
i.A. reichen DPDAs, zur syntaktischen Analyse aus
L={anbnam}u{ambnan}wird von NPDAs erkannt, aber nicht von DPDAs
Kellerautomat (PushDownAutomaton)
kontextfreie Grammatiken
wichtigste Beschreibungsart für die Syntax von Programmiersprachen ( Ausdruck, Kontrollstrukt.)
erzeugen die kontextfreien Sprachen (Typ-2)
gleichwertige Beschreibungsarten:
Backus-Naur-Formen
Syntaxdiagramme
Produktionen kontextfr. Grammatiken
Alle Regeln haben die Form:
N → α
als linke Regelseite sind nur einzelne Nichtterminale erlaubt
so kann ein Nichtterminalsymbol unabhängig 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={anbn}, die keine reguläre Sprache ist
kontextfreie Grammatiken können mehrdeutig sein
x+y*z →(x+y) *z oder x+(y*z)
kontextsensitive Sprache (Typ-1)
formale Sprache, die von einer kontextsensitiven Grammatik erzeugt, und von linear beschränkten 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 Länge des Arbeitsbandes durch die Länge des Eingabewortes beschränkt sein
sie sind mächtiger als kontextfreie Sprachen
z.B. ist die Sprache L = {an bn cn } nicht kontextfrei
Allgemeine Sprachen (Typ-0)
Sprachen, die von Grammatiken ohne Einschränkungen erzeugt werden können
sie werden von Turingmaschinen (und damit auch von Computern) erkannt
Chomsky-Hierarchie:Ent : Entscheidbare SprCS : KontextsensitivCF : KontextfreiLin : Lineare Grammat.DPDA: det.KellerautomatRL : reguläre SpracheTM: TuringmaschineAuf: aufzählbare Spr.NLBA: nichtdeterminist. lin. beschr. AutomatNPDA: nichtdeterminist. push-down-automatonRL : rechtslinearLL : linkslinearEA : endlicher Automat