Finden der oberen Zustandsgrenze in minimal deterministischen endlichen Automaten

Question

Ich habe die Aufgabe, die Obergrenze der Zustände im zu bestimmen Minimale deterministische endliche Automaten das erkennt das Sprache: $ L (a_1) backslash l (a_2) $, Wo $ A_1 $ ist ein deterministischer endlicher Automat (DFA) mit $n$ Staaten und $A_2$ ist Nichtdeterministische endliche Automaten (NFA) mit $m$ Zustände.

So versuche ich das Problem zu lösen:

1. $ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, das ist die Sprache, die von einem Automaten erkannt wird $L'$ mit $nm$ Zustände.
2. Bestimmung von $L'$ was hat $(nm)^2$ Staaten und es ist die Obergrenze der Staaten.

Habe ich recht?

Answer 1

Das ist falsch.Bestimmung eines NFA mit $r$ Staaten könnten zu einem DFA mit bis zu führen $2^r$ Zustände.Daher gibt Ihr Argument tatsächlich eine Obergrenze von an$$2^{nm}.$$Dies kann verbessert werden, wenn Sie die Reihenfolge der Vorgänge ändern.Wenn Sie Ihre NFA zunächst in eine DFA umwandeln und erst dann die Produktkonstruktion anwenden, erhalten Sie die bessere Bindung$$ n2^m.$$

Diese Schranke ist für unendlich viele Werte von eng $n,m$.Betrachten Sie die Sprache $L_2$ aller Worte vorbei $\Sigma^*\{\sigma_1,\ldots,\sigma_2\}$ Das nicht alle Buchstaben enthalten.Es gibt eine NFA für $L_2$ (mit mehreren Anfangszuständen) nur mit $m$ Zustände.Allerdings ist jede NFA für $\overline{L_2}$ muss mindestens enthalten 2^m$ Zustände.Seit $\overline{L_2} = \Sigma^* \setminus L_2$ Und $\Sigma^*$ von einem Einzelstaat-DFA akzeptiert werden kann, sehen wir, dass die obige Grenze optimal ist.

Sie können wahrscheinlich zeigen, dass die Grenze für (praktisch) alle eng ist $n,m$ indem man die obige Konstruktion leicht modifiziert, ersetzt $\Sigma^*$ mit $(\Sigma^n)^*$.