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.

Def. Akzeptiertes Wort einer TM

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

Def. Durch Endzustand akzeptiertes Wort einer NDKA

Ein NDKA $\mathcal{P}$ akzeptiert ein Wort $w$ durch Endzustand, falls ein Berechnung von $\mathcal{P}$ auf $w$ existiert so, dass der Zustand $q_m$ der Endkonfiguration ein Endzustand ist, also $q_m\in F\;.$

Def. Durch leeren Keller akzeptiertes Wort einer NDKA

Ein NDKA $\mathcal{P}$ akzeptiert ein Wort $w$ durch leeren Keller, falls ein Berechnung von $\mathcal{P}$ auf $w$ existiert so, dass der Inhalt des Kellerspeicher in der Endkonfiguration $\beta$ leer ist, also $\beta = \varepsilon\;.$