Theoretische Informatik
Mensch – Maschine - Kommunikation
Menschen benutzen Sprachen
zur Kommunikation
Computer verstehenInformationen in Binär-CodeCompiler
Theoretische Informatik
Theorie der formalen Sprachen
Wir brauchen eine Sprache,
die eindeutig in Maschinensprache
(Binär-Code) übersetzt werden
kann.Menschen benutzen
Sprachenzur Kommunikation
Theoretische Informatik
Automatentheorie
Computer verstehenInformationen in Binär-CodeCompiler
Wir brauchen einen Compiler (Automat),der die Sprache in
Maschinensprache (Binär-Code)übersetzt.
Theoretische Informatik
Automatentheorie
Theorie der formalen Sprachen
bedeutende Teilbereiche:
Theoretische Informatik
Der Hnud jagt die Katze.
formaleSprachen
Rechtschreibfehler
Alle Wörter werden auf korrekte Rechtschreibung
kontrolliert.
Die Grundlage dafür bildet der Duden.
1. Lexikalische Analyse
Theoretische Informatik
Der Hund die Katze jagt.
formaleSprachen
Grammatikfehler (SPO)
Der Text wird auf Korrekte sprachliche Form
kontrolliert.
Die Grundlage dafür bildet die Grammatik.
2. syntaktische Analyse
Theoretische Informatik
Öffne die Datei mit dem Editor.
formaleSprachen
Dieser Satz hat unterschiedliche Bedeutungen:
3. semantische Analyse
Adverbial zu „öffnen“: Wie soll die Datei geöffnet werden ?
Attribut zu „Datei“: Welche Datei soll geöffnet werden ?
Theoretische Informatik
formaleSprachen
Bei natürlicher Sprache sind einzelne Wörter oder Sätze
erst im gesamten Textzusammenhangverständlich.
In manchen Texten kann und muss man auch„zwischen den Zeilen“ lesen.
Theoretische Informatik
formaleSprachen
Deshalb :
Natürliche Sprachen sind für die Programmierungnicht geeignet !
Theoretische Informatik
formaleSprachen
Definitionen :
Ein Alphabet ist eine endliche, nichtleere Menge von Symbolen (Buchstaben).
Alphabet
Theoretische Informatik
formaleSprachen
Definitionen :
Sei V ein Alphabet und k lN0.Eine endliche Folge x1 x2...xk mit xi V (i = 1, ..., k)heißt Wort über V der Länge k.
Wörter
Die Länge eines Wortes x wird durch |x| dargestellt.
Es gibt ein Wort mit der Länge 0, das leere Wort.Das leere Wort wird mit bezeichnet.
Theoretische Informatik
formaleSprachen
Definitionen :
Sei V ein Alphabet.
V* bezeichnet die Menge aller Wörter über V.
V+ bezeichnet die Menge der nichtleeren Wörter über V.
V+ = V* \ { }
Sprache
Jede beliebige Teilmenge von V* wird als Sprache oderformale Sprache bezeichnet.
Theoretische Informatik
formaleSprachen
Beispiele :
V = { 0, 1 }
Alphabet :
Wörter :
0011 01010 00000 11111
Sprache :
L = Menge aller Binärzahlen ohne führende Nullen = { 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... }
Theoretische Informatik
formaleSprachen
Beispiele :
V = { 1 }
Alphabet :
Wörter :
1 11 111 11111
Sprache :
L = Menge der nat. Zahlen in unärer Darstellung = { 1, 11, 111, 1111, ... }
Theoretische Informatik
formaleSprachen
Beispiele :
V = { 0, 1, 2, 3, ..., 9 }
Alphabet :
Wörter :
1 37109 732
Sprache :
L = Menge der nat. Zahlen in Dezimalschreibweise = { 0, 1, 2, 3, ... }
Theoretische Informatik
formaleSprachen
Beispiele :
V = { a, b, ..., z, ä, ö, ü, ß, A, B, ..., Z, Ä, Ö, Ü }
Alphabet :
Wörter :
Urlaub Schule Informatik
Sprache :
L = Die Menge aller Einträge im Duden
Abitur Ferein
Theoretische Informatik
formaleSprachen
Beispiele :
V = Menge aller Einträge im Duden
Alphabet :
Wörter :
Der Ball ist rund
Sprache :
L = Die deutsche Sprache in grammatikalisch richtigen Sätzen
Der auch ist gut
Theoretische Informatik
formaleSprachen
Beispiele :
V = der ASCII-Zeichensatz
Alphabet :
Wörter :
while
Sprache :
L = Alle Token (Schlüsselwörter, Begrenzer, Bezeichner, Literale und Operatoren) der Programmiersprache C++
( operand1 <100
Scanner
Lexikalische Analyse
Theoretische Informatik
formaleSprachen
Beispiele :
V = Token der Programmiersprache C++
Alphabet :
Wörter :
void main() { cout << “Hello world !\n“; }
Sprache :
L = Alle syntaktisch richtigen C++ - Programme
Parser
Syntaktische Analyse
Theoretische Informatik
Automaten-theorie
Zigaretten-Automat
3,- €
Rückgabe
Zigaretten
HB
Ern
te 2
3
Marl
boro
ug
h
R6
Reval
Ste
yvesa
nt
Eingaben:
Interne Zustände:
Ausgaben:
1 €
R-Taste Wahl -Tasten
HB
Zigaretten
HB 1 €
Zigaretten+
Wechselgeld
2 €
1 €
Geldrückgabe
Kein Geld eingegeben
1 € ist eingegeben
2 € sind eingegeben
3 € sind eingegeben
4 € sind eingegeben
2 €
Beispiel :
Theoretische Informatik
Automaten-theorie
Zustandsveränderungen hängen ab von den Eingaben:
Beispiel :
Zustände:
q0 : Kein Geld eingegeben
q1 : 1 € ist eingegeben
q2 : 2 € sind eingegeben
q3 : 3 € sind eingegeben
q4 : 4 € sind eingegeben
Zustandsüberführungstabelle:
q0
q1
q2
q3
q4
1 € R-Taste Wahl -Tasten
2 €
q1 | -- q2 | --
q2 | --
q3 | --
q3 | --
q4 | --
q4 | 1 €
q3 | 1 €
q3 | 2 €
q4 | 2 €
q0 | -- q0 | --
q1 | --
q2 | --
R6q0 |
1 €
HBq0 |
q0 | 1 €
q0 | 2 €
2 €
q0 | 2 €
1 €
q0 | 2 €
Theoretische Informatik
Automaten-theorie
Zustandsveränderungen hängen ab von den Eingaben:
Beispiel :
Zustände:
q0 : Kein Geld eingegeben
q1 : 1 € ist eingegeben
q2 : 2 € sind eingegeben
q3 : 3 € sind eingegeben
q4 : 4 € sind eingegeben
Zustandsüberführungsgraph:
q0
1,- | --
HB
q1 q3
q4q2
2,- | --R-Taste | 1
,-
2,- | --
2,- | --
1,- | -- 1,- |
--
R-Taste | 3,-
R-Taste | 4,-
R-Taste | 2,-
Wahl -Taste |
Wahl -Taste | 1,- HB
Theoretische Informatik
Automaten-theorie
Ein Automat
- hat interne Zustände, die wechseln können
- bekommt Eingaben
- liefert gegebenenfalls Ausgaben
Theoretische Informatik
Automaten-theorie
Wir brauchen Automaten, die Wörter bzw. Sprachen erkennen können.
(Scanner, Parser)
Solche Automaten liefern keine Ausgabe,sie halten einfach nach Eingabe eines Wortes an.
Befindet sich der Automat nach vollständiger Eingabeeines Wortes in einem „Endzustand“,
so wird das Wort „akzeptiert“.
Theoretische Informatik
Automaten-theorie
Zustandsüberführungsgraph eines endlichen Automaten
Beispiel :
q0
q3
0
1
0|1 0|1
0|1q2
q1
Zustände : Z={ q0, q1, q2, q3 }
Eingabealphabet : V={ 0, 1 }
Startzustand : q0
Endzustände : F={ q1, q2 }
akzeptierte Wörter : 0 1 1101 10101011
nicht akzeptierte Wörter : 00 01 01101 0101011
Sprache : L = Menge aller Binärzahlen ohne führende Nullen = { 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... }