Zeichnen Sie den minimalen DEA, der alle Worte über {a, b} akzeptiert, die eine gerade Anzahl von a’s (inklusive leeres Wort) haben. Zeichnen Sie auch den minimalen DEA, der Worte über {a, b} mit einer ungerade Anzahl b’s akzeptiert. Fassen Sie beide Automaten als einen NEA auf, der zwei mögliche Startzustände besitzt und offensichtlich alle Worte akzeptiert, die eine gerade Anzahl a’s oder ungerade Anzahl b’s enthalten.
Konstruieren Sie dann mit der Teilmengenkonstruktion und der Untersuchung auf äquivalente Zustände den minimalen DEA.