Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
|
informatik-buch:theoretische_informatik:start [2009/04/26 11:20] |
informatik-buch:theoretische_informatik:start [2009/04/26 11:20] (aktuell) |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| + | ====== Theoretische Informatik ====== | ||
| + | Dieses Kapitel ist (und bleibt vermutlich auch noch länger) nicht wirklich überschaubar strukturiert und der Inhalt lässt mehr als zu Wünschen übrig. Ich habe das alles noch nie unterrichtet und schreibe es nur auf, damit ich beim Lernen noch weiß, was ich alles gemacht habe. | ||
| + | |||
| + | * [[.:Formale Sprachen:]] - [[.:Formale Sprachen:Sprachbeschreibung]], [[.:Formale Sprachen:Spracherkennung]], [[.:Formale Sprachen:Reguläre Sprachen]], [[.:Formale Sprachen:Kontextfreie Sprachen]], [[.:Formale Sprachen:Kontextsensitive Sprachen]] (XML) | ||
| + | * [[.:Grenzen der Berechenbarkeit:]] | ||
| + | * [[Automatensimulator]] | ||
| + | * [[Stapel]] / Keller | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Turingmaschine, Kellerautomat | ||
| + | |||
| + | Chomsky-Hierarchie | ||
| + | | Typ 0 | allgemein | äquivalenter Automat | | ||
| + | | Typ 1 | kontextsensitiv | nichtdeterministischer linear beschränkten Turingmaschine | | ||
| + | | Typ 2 | kontextfrei | nichtdeterministischer Kellerautomat | | ||
| + | | Typ 3 | regulär | (nicht)deterministischer endlicher Automat | | ||
| + | |||
| + | Eine Sprache ist allgemein genau dann, wenn sie von einer deterministischen (oder nichtdeterministischen) Turingmaschine erkannt wird. | ||
| + | |||
| + | Eine Sprache ist kontextsensitiv genau dann, wenn sie von einer linear beschränkten nichtdeterministischen Turingmaschine erkannt wird. | ||
| + | |||
| + | == Natürliche Sprachen == | ||
| + | ^ Syntax | Lehre vom Satzbau, Anordnung der Zeichen | | ||
| + | ^ Semantik | Bedeutungslehre, Beziehung zwischen Zeichen und Bezeichnetem | | ||
| + | ^ Pragmatik | Lehre von der Verwendung sprachlicher Konstrukte in Handlungssituationen - Beziehung zwischen Zeichen und Zeichenbenutzer | | ||
| + | |||
| + | ====== Semantik von Programmiersprachen ====== | ||
| + | ===== Scanner und Parser ===== | ||
| + | |||
| + | - Syntax analyse | ||
| + | - Scanner: aus Zeichenfolgen lexikalische Einheiten bilden und als Tokenfolge aufzubereiten | ||
| + | - Scanner-Automat: nutzt endlichen Automat zur Erkennung der lexikalischen Einheiten | ||
| + | - Parser: Tokenfolge auf syntaktische Korrektheit prüfen (evtl. Tokenfolge aufbereiten) | ||
| + | - Parser-Automat: nutzt Kellerautomaten zur syntaktischen Analyse der Tokenfolge | ||
| + | - Interpreter: führt Anweisungen Schritt für Schritt aus | ||
| + | |||
| + | Eine präzise Interpreter-Beschreibung kann somit zur Festlegung der Semantik der Elemente der Programmiersprache benutzt werden (**Interpreter-Semantik**). | ||
| + | |||
| + | Transformationsregeln?? | ||
| + | |||
| + | ===== Übersetzer ===== | ||
| + | transformieren Programme der Ausgangs-Programmiersprache (Quellsprache) in eine andere Sprache (Zielsprache). | ||
| + | |||
| + | Eine präzise Übersetzer-Beschreibung kann zur Festlegung der Semantik | ||