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

Sprachklasse	Berechnungsmodell	Wortproblem
Type 0	Turingmaschine \(TM\)	semi(oder nicht-)entscheidbar
Type 1, Kontextsensitiv	Nondeterministische TM mit linearem Speicher	PSpace-vollständig
Type 2, Kontextfrei	Nondeterministic Pushdown Automaton	Polynomiell
Type 3, Regulär	endlicher Automat	Polynomiell

the comment system on this blog works via email. The button
below will generate a mailto: link based on this page's url 
and invoke your email client - please edit the comment there!

[optional] even better, encrypt the email with my public key

- don't modify the subject field
- specify a nickname, otherwise your comment will be shown as   
  anonymous
- your email address will not be disclosed
- you agree that the comment is to be made public.
- to take down a comment, send the request via email.