Akzeptiertes Wort

Einfache Sprache

Ist die Eingabe eines Endlicher Automat ein Akzeptiertes Wort, so wird der EA in einem Endzustand enden.

Def. Akzeptiertes Wort eines DEA

Sei $A$ ein Alphabet und $x\in A^*$. Dann wird $x$ von einem DEA $M=(Q,A,\delta,q_I,F)$ akzeptiert, wenn

$$\hat\delta(q_I,x)\in F\;.$$

Def. Akzeptiertes Wort eines NEA

Ein NEA $\mathcal{A}$ akzeptiert ein Wort $w$, falls ein akzeptierte Berechnung von $\mathcal{A}$ auf $w$ existiert.