Grammatiken beschreiben Sprachen als Menge von Wörern, die sie erzeugen können.
Aufgabe: erkenne ob ein Wort in einer Sprache liegt.

English Version of this post
NOTE: MOST CONTENT OF THIS POST ARE TAKEN FROM:

Lecture scripts by Prof. Dr. Markus Krötzsch, TU Dresden

§ das Wortproblem

Das wortproblem für eine Sprache L über ALphabet $\Sigma$ besteht darin, die folgende Funktion zu berechnen:

• Eingabe: ein Wort $w \in \Sigma^\star$
• Ausgabe: ja wenn $w \in L$ , nein wenn $w \notin L$

This is also referred to as the Decision Problem.

§ Entscheidbarkeit

Eine Sprache $L \in \Sigma^\star$ ist entscheidbar, wenn ihre Eigenschaftsfunktion: $\chi_L: \Sigma^\star \to \{0,1\}$ berechenbar: für jedes gegeben Wort, man kann entscheiden, ob es in L liegt.

Eine Sprache $L \in \Sigma^\star$ is semi-entscheidbar: man kann sicher Ja sagen, wenn ein gegebenes Wort in L liegt, aber man weiß nicht, ob ein Wort NICHT in L liegt.

Oder vice versa:

§ Komplexität und Berechnungsmodell

Ausblick