Wortproblem endlicher Automaten

Gegeben:

• Ein endliches Alphabet $\mathrm{\Sigma }$.
• Ein endlicher, nicht-deterministischer Automat $\mathcal{A}=(Q,\mathrm{\Sigma },q_0,\mathrm{\Delta },F)$.
• Ein Wort $w\in {\mathrm{\Sigma }}^{\ast }$.

Problem:
Entscheide, ob $\mathcal{A}$ das Wort $w$ akzeptiert (Ausgabe 1), sonst 0.

Zusammenhang zu SAT:
Für jedes endliche $w$ und reguläre Sprache $\mathcal{L}$ kann dieses Problem in Polynomialzeit auf SAT reduziert werden. Man konstruiert eine Formel ${\phi }_w$, die genau dann erfüllbar ist, wenn $w\in \mathcal{L}(\mathcal{A})$.