Wortproblem (Berechenbarkeitstheorie)

Als Wortproblem einer formalen Sprache L bezeichnet man in der Informatik das Entscheidungsproblem, zu einem gegebenen Wort zu entscheiden, ob dieses zur Sprache gehört oder nicht. Da sich umgekehrt jedes Entscheidungsproblem als Wortproblem einer formalen Sprache auffassen lässt, sind die beide Begriffe sehr eng verwandt.

siehe auch: Optimierungsproblem, Suchproblem