Minimaler DEA

Einfache Sprache

Def. Minimaler DEA

Gegeben ein DEA $\mathcal A = (Q,A,\delta,q_I,F)$ mit $L=L(\mathcal A)$.

Sei $P$ die Partition, die der Algorithmus conflictFreePartition für $\mathcal A$ zurück gibt und $\equiv$ ist die Äquivalenzrelation die $P$ entspricht. Wir definieren $\mathcal A' = (Q' = P,A,\delta',q_I',F')$ mit

• $q_I' = [q_I]_\equiv$,
• $F' = \{[q]_\equiv:q\in F\}$ und
• $\forall q\in Q,a\in A:\delta'([q]_\equiv, a) = [\delta(q,a)]_\equiv$.

Dann gilt

• $\mathcal A'$ ist wohl definiert.
• $\mathcal A'$ erkennt $L$.
• $\mathcal A'$ ist ein minimaler DEA bzgl der Größe von $Q$, der $L$ erkennt.
• $\mathcal A'$ ist isomorph zu allen anderen minimalen DEAs von $\mathcal A$.