Wortproblem

Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört, oder nicht. Das Wortproblem einer Sprache ist entscheidbar, wenn ihre charakteristische Funktion  berechenbar ist. Sie ist definiert durch