„Das ''Wortproblem'' für endliche Automaten ist in Linearzeit entscheidbar.“<ref>{{Literatur |Autor=Renate Winter |Titel=Theoretische Informatik |TitelErg=Grundlagen mit Übungsaufgaben und Lösungen |Verlag=Oldenbourg |Ort=Wien |Jahr=2002 |ISBN=3-486-25808-7 |Seiten=149 |Online=[http://books.google.de/books?id=EB7Cdjcw54QC&pg=PA149&hl=de&sa=X Online-Version]}}</ref>
''[[Informatik]]:'' die Frage, ob ein gegebenes Wort zu einer [[formale Sprache|formalen Sprache]] gehört