3.1 Einstieg & Definition
Wofür braucht es den Begriff der Sprache?
Wörter verwenden wir üblicherweise zur Darstellung gewisser Objekte, wie zum Beispiel von Zahlen, Graphen, Diagrammen und Texten. Eine Sprache kann dazu dienen, die Darstellung von Objekten mit einer gegebenen Eigenschaft in eine Klasse einzuordnen.
Zum Beispiel können wir die Sprache \(L_{prim}\) als die Menge aller Primzahlen definieren. Für eine biologische Anwendung können wir die Sprache \(L_{ACCTTAx}\) als die Menge aller DNA-Sequenzen, die mit ACCTTA beginnen, definieren.
In der Informatik verwenden wir Sprachen zum Lösen von Entscheidungsproblemen. Beispielsweise nehmen wir das Entscheidungsproblem “Ist 2021 eine Primzahl?” Wenn wir nun die Sprache \(L_{prim}\) haben, können wir testen ob \(2021 \in L_{prim}\) gilt.
Definition: Entscheidungsproblem
Sei eine Sprache \(L\) über einem Alphabet \(Σ\) gegeben. Das Entscheidungsproblem \((Σ,L)\) ist die folgende Berechnungsaufgabe:
Input: Eine Sprache \(L\) und ein Wort \(x \in Σ^*\)
Output: JA, falls \(x \in L\) , und NEIN, falls \(x \notin L\)
Beispiel
Gegeben: Alphabet \(Σ = \{0, 1, 2, 3, …,9\}\), Sprache \(L_{prim}\) und zu testende Wörter \(x\) aus \(Σ^*\).
Der Test, ob \(x\) eine Primzahl darstellt, ist äquivalent zu der Entscheidung, ob \(x \in L_{prim}\)gilt.
Lösungsmechanismen
In den nachfolgenden Abschnitten werden wir akzeptierende und beschreibende Lösungsmechanismen für Entscheidungsprobleme kennen lernen. Was genau damit gemeint ist und wie diese funktionieren, finden wir ebenfalls in den folgenden Abschnitten. Weiter existieren auch sogenannte generierende Lösungsmechanismen, diese werden wir noch nicht behandeln.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 3_1_entscheidungsprob_Notizen.