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.

$$ \chi_L(w) = \begin{cases}1 , &w \in L \\0 , &w \notin L \end{cases} $$

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.

$$ \chi_L(w) = \begin{cases} 1 , &w \in L \\ \text{undefined}, &w \notin L\end{cases} $$

Oder vice versa:

$$ \chi_L(w) = \begin{cases} \text{undefined}, &w \in L\\ 0 , &w \notin L \end{cases} $$

Komplexität und Berechnungsmodell

Ausblick