Reduzierte Automaten

Id: reduz.tex,v 1.3 2005/10/26 21:31:59 waldmann Exp

Ein Zustand q eines Automaten A heißt

• erreichbar, falls von q von einem Startzustand aus erreichbar ist: $\exists$w $\in$ $\Sigma^{*}_{}$, s $\in$ S(A) : s$\;\stackrel{{w}}{{\to}}\;$q.
• produktiv, falls von q aus ein akzeptierender Zustand erreichbar ist: $\exists$w $\in$ $\Sigma^{*}_{}$, f $\in$ F(A) : q$\;\stackrel{{w}}{{\to}}\;$f.
• nützlich, wenn er erreichbar und produktiv ist.

A heißt reduziert, wenn alle Zustände nützlich sind.

Satz: Zu jedem Automaten A gibt es einen reduzierten Automaten B mit L(A) = L(B).

Beweis:
erst A auf erreichbare Zustände einschränken, ergibt A',
dann A' auf produktive Zustände einschränken, ergibt B.