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