Das Wortproblem und Berechnungsmodell

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

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.


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


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
Nov 16, 2020

[+] click to leave a comment [+]
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   
- 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.


Fun with Image Maps and SVGs via benji February 20, 2024

Over the past few weeks I've been playing around with making some images on my website interactive. My "informatics" class in high school taught us some basic HTML. By basic I mean in notepad and writing everything by hand, saving to a...

Goblin Week 2024 via Helvetica Blanc January 26, 2024

It snuck up on me, but I managed to draw my little goblins to celebrate the week! I love my children - they're like awful Pikmin. I've uploaded the whole parade as a print, as well as individual prints for each goblin. There's something very fu…

How to trust gpg keys via Travis Shears Personal Site October 27, 2023

After moving some GPG keys to a new computer I kept getting these trust warnings. It is NOT certain that the key belongs to the person named in the user ID.If you * really * know what you are doing, you may answer the next question with yes. Use this key a…

Generated by openring from webring