7298978
Description
Flashcards by Luca Rolshoven, updated more than 1 year ago
|
Created by Luca Rolshoven
almost 8 years ago
|
|
| Question | Answer |
| Formale Sprache | Menge von Wörtern, die aus einem gegebenen Alphabet gebildet werden. Auf diesen Wörtern können Operationen definiert werden, die unter Umständen zu neuen Wörtern führen. |
| Syntax | Legt fest, auf welche Weise die Wörter gebildet werden können und welche Operationen mit den Wörtern durchgeführt werden dürfen. Sie regelt die rein formalen Beziehungen zwischen Zeichen und Wörtern. |
| Semantik | Interpretiert die Zeichen und Wörtern und gibt ihnen in diesem Sinn eine Bedeutung. Diese Bedeutung wird dabei durch Regeln explizit festgelegt. |
| Beispiele von formalen Sprachen | - CPL (klassische Aussagenlogik) - FOL (Classical First Order Logic) - Übliche Programmiersprachen etc. |
| Verschiedene Arten von Semantik | - Wahrheitsfunktionale Semantik: Bedeutung des Satzes = ist er wahr? - Algebraic Semantics: Algebraische Beschreibung von Datentypen, Programmiersprachen, Programmschritte, etc. - Denotational Semantics: Einem Programm π wird eine Funktion ⟦π⟧ als Bedeutung zugeordnet, die Inputs auf Outputs abbildet. - Operational Semantics: "Verhalten" von Systemen und Programmen, welche als Folge von einzelnen Berechnungsschritten verstanden werden, wird mathematisch beschrieben. - Axiomatic Semantics: Bedeutung Befehl = Effekt, die der Befehl auf Aussagen über Programmzustand ausübt; {A}π{B}: Gilt A vor Ausfuhrung von π, so gilt B nach Ausfuhrung von π |
| Ausgangsalphabet CPL | Atomare Propositionen: U, V, W, U0, U1, etc Logische Konnektive: ¬,∨,∧, → Weitere Hilfsmittel: Klammern, Kommas |
| CPL Syntax | 1. Jede atomare Propositon ist eine Formel von CPL. 2. Ist A eine Formel von CPL, so auch ¬A 3. Sind A,B Formel von CPL, so auch (A ∨ B), (A ∧ B) sowie (A → B) |
| Länge einer CPL-Formel | Die Länge l(A) einer Formel A von CPL verstehen wir als die Anzahl der Vorkommnisse der atomaren Propositionen und logischen Konnektive in A. |
| CPL Semantik | Wahrheitsfunktionale Semantik. Jeder Proposition wird "wahr" oder "falsch" zugeordnet (Propositionenbelegung). |
| Gültigkeit | Eine Formel A von CPL heisst gültig, falls die Formel für alle möglichen Propositionenbelegungen wahr ist. (Auch: Tautologie) |
| Erfüllbarkeit | Eine Formel von CPL heisst erfüllbar, falls es eine Propositionenbelegung gibt, so dass die Formel wahr ist. |
| Erfüllbarkeitsproblem aussagenlogischer Formeln | Eines der bedeutesten ungelösten P-NP-Problemen. Kann die Erfüllbarkeit von CPL-Formeln in polynomialer Zeit getestet werden? Das Problem ist äquivalent zu einer Reihe von kombinatorischen Problemen (z.B. TSP) |
| Warum ist WHILE von Interesse? (die Sprache) | - Einige zentrale Aspekte von Programmiersprachen lassen sich paradigmatisch diskutieren - Computationally Complete: Jedes (berechenbare) Programm kann in WHILE realisiert werden. |
| Ausgangsalphabet WHILE | Variablen: X0, X1, X2, ... Grundzeichen: 0, S, P, ←, ≠, ; , (, ), while, do, od |
| Definition (Wertzuweisung) in WHILE | |
| Für ein WHILE-Programm σ: Was bezeichnet Var(σ)? | Menge aller Variablen, die in σ auftreten. |
| Länge eines WHILE-Programms σ | |
| Denotationelle WHILE-Semantik | |
| Definition (WHILE-Semantik) | |
| Beispiel: Schleife in WHILE | while X0 ≠ 0 do X0 ← S(X0) od Solange X0 nicht Null ist, erhöhe X0 um 1. |
Want to create your own Flashcards for free with GoConqr? Learn more.