Flashcards
Syntax und Semantik formaler Sprachen
Flashcards do conjunto (20)
- 1Formale SpracheMenge 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.
- 2SyntaxLegt 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.
- 3SemantikInterpretiert die Zeichen und Wörtern und gibt ihnen in diesem Sinn eine Bedeutung. Diese Bedeutung wird dabei durch Regeln explizit festgelegt.
- 4Beispiele von formalen Sprachen- CPL (klassische Aussagenlogik)
- FOL (Classical First Order Logic)
- Übliche Programmiersprachen
etc. - 5Verschiedene 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 π - 6Ausgangsalphabet CPLAtomare Propositionen: U, V, W, U0, U1, etc
Logische Konnektive: ¬,∨,∧, →
Weitere Hilfsmittel: Klammern, Kommas - 7CPL Syntax1. 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) - 8Länge einer CPL-FormelDie Länge l(A) einer Formel A von CPL verstehen wir als die Anzahl der Vorkommnisse der atomaren Propositionen und logischen Konnektive in A.
- 9CPL SemantikWahrheitsfunktionale Semantik.
Jeder Proposition wird "wahr" oder "falsch" zugeordnet (Propositionenbelegung). - 10GültigkeitEine Formel A von CPL heisst gültig, falls die Formel für alle möglichen Propositionenbelegungen wahr ist.
(Auch: Tautologie) - 11ErfüllbarkeitEine Formel von CPL heisst erfüllbar, falls es eine Propositionenbelegung gibt, so dass die Formel wahr ist.
- 12Erfüllbarkeitsproblem aussagenlogischer FormelnEines 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) - 13Warum 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. - 14Ausgangsalphabet WHILEVariablen:
X0, X1, X2, ...
Grundzeichen:
0, S, P, ←, ≠, ; , (, ), while, do, od - 15Definition (Wertzuweisung) in WHILE
- 16Für ein WHILE-Programm σ: Was bezeichnet Var(σ)?Menge aller Variablen, die in σ auftreten.
- 17Länge eines WHILE-Programms σ
- 18Denotationelle WHILE-Semantik
- 19Definition (WHILE-Semantik)
- 20Beispiel: Schleife in WHILEwhile X0 ≠ 0 do X0 ← S(X0) od
Solange X0 nicht Null ist, erhöhe X0 um 1.
Informações
- Descrição
- Syntax und Semantik formaler Sprachen
- Criado por
- Luca Rolshoven
- Visualizações
- 17
- Avaliação