Reduzieren eines DFA zu einem NFA

Question

Ich versuche, ein Problem herauszufinden, wo ich ein NFA für eine bestimmte Sprache zeichnen muss.

Die Sprache ist { w | the final five symbols of w include two a's and three b's }.

Ich glaube, ich habe es als DFA und bin mir nicht sicher, ob es eine reduzierte Version gibt. Wenn jemand einen Blick darauf werfen könnte, wäre das sehr hilfreich. Ich habe das Gefühl, dass es zu einem ziemlich kleinen NFA reduziert werden kann.

Answer 1

Zunächst einmal, was Sie haben kein DFA ist; a Zustand ist eindeutig nicht deterministisch:

• mit einem a Sie sowohl a und b gehen
• mit einem b Sie bekamen beide können a und s

Zweitens, da in einer FSA Sie kann nur mit Zuständen zählen (es gibt keinen Stapel), Sie müssen verfolgen, wie viele von jedem Symbol Sie in den letzten 5 Zeichen im Statusbereich gesehen haben. Denken Sie nur darüber nach, wie viele verschiedene Kombinationen Sie benötigen, und dann werden die Übergänge offensichtlich. Das ist die kleinste NFA, mit der du diese Übung lösen kannst.