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 L ist entscheidbar, wenn ihre charakteristische Funktion \chi _{L} berechenbar ist, welche definiert ist durch

{\displaystyle \chi _{L}\colon \Sigma ^{\ast }\to \{0,1\};\ w\mapsto {\begin{cases}1,&{\text{falls }}w\in L\\0,&{\text{sonst}}\end{cases}}}

Die Sprache L hat also ein entscheidbares Wortproblem, wenn es einen Algorithmus gibt, der in endlicher Zeit herausfindet, ob w\in L oder nicht. Jedes Entscheidungsproblem lässt sich als Wortproblem einer formalen Sprache codieren.

Die Schwierigkeit des Wortproblems hängt von der zugrunde gelegten Klasse der Sprachen ab. Für die Chomsky-Hierarchie ist bekannt:

Siehe auch

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 22.07. 2022