Man betrachte nichtdeterministische endliche Automaten und eine Funktion . Zusätzlich definieren wir .
Analysieren wir nun die folgende Aussage:
Wenn , dann ist .
Es ist leicht zu zeigen, dass für gilt, wenn also die Automaten jedes Wort mit einer Länge von bis zu erzeugen Q | + 1 , dann erzeugt es .
Aber gilt es immer noch, wenn ein Polynom ist?
Wenn nicht, was könnte eine Konstruktion eines NFA für ein bestimmtes polynom aussehen, st ?
Antworten:
Damit die Anweisung gültig ist, muss f exponentiell wachsen, auch mit dem unären Alphabet.
[Bearbeiten: Die Analyse wurde in Revision 2 leicht verbessert.]
Hier ist eine Beweisskizze. Angenommen, die Anweisung gilt und f sei eine Funktion, bei der jede NFA mit höchstens n Zuständen, die alle Zeichenfolgen mit der Länge höchstens f ( n ) akzeptiert, alle Zeichenfolgen überhaupt akzeptiert. Wir werden beweisen , dass für jede C > 0 und ausreichend groß n , haben wir f ( n )> 2 C ⋅√ n .
Der Primzahlsatz impliziert, dass es für jedes c <lg e und für ausreichend großes k mindestens c ⋅ 2 k / k Primzahlen im Bereich [2 k , 2 k +1 ] gibt. Wir nehmen c = 1. Für ein solches k sei N k = ⌈2 k / k ⌉ und definiere ein NFA M k wie folgt. Sei p 1 ,…, p N k verschiedene Primzahlen im Bereich [2 k , 2 k +1]. Die NFA M k hat S k = 1 + p 1 +… + p N k Zustände. Abgesehen vom Anfangszustand sind die Zustände in N k Zyklen unterteilt, wobei der i- te Zyklus die Länge p i hat . In jedem Zyklus sind alle bis auf einen Zustand akzeptierte Zustände. Der Anfangszustand hat N k ausgehende Flanken, von denen jede in jedem Zyklus unmittelbar nach dem zurückgewiesenen Zustand in den Zustand übergeht. Schließlich wird auch der Ausgangszustand übernommen.
Sei P k das Produkt p 1 … p N k . Es ist leicht zu sehen , dass M k alle Strings der Länge kleiner als akzeptiert P k lehnt aber die Zeichenfolge der Länge P k . Daher ist f ( S k ) ≥ P k .
Man beachte , daß S k ≤ 1 + N k ⋅2 k +1 = O (2 2 k ) ist und daß P k ≥ (2 k ) N k ≥ 2 2 k . Der Rest ist Standard.
quelle
BEARBEITEN AM 12.10.06:
ok, das ist so ziemlich die beste Konstruktion, die ich bekommen kann. Mal sehen, ob jemand bessere Ideen hat.
Dies ergibt .f(n)=Ω(2n/5)
Die Konstruktion ist mit der in Shallit ziemlich identisch , außer dass wir eine NFA direkt konstruieren, anstatt die Sprache zuerst durch einen regulären Ausdruck darzustellen. Lassen
.Σ={[00],[01],[10],[11],♯}
The idea is that we can construct an NFA consists of five parts;
Note that we do want to acceptΣ∗−{sn} instead of {sn} , so once we find out that the input sequence is disobeying one of the above behaviors, we accept the sequence immediately. Otherwise after |sn| steps, the NFA will be in the only possible rejecting state. And if the sequence is longer than |sn| , the NFA also accepts. So any NFA satisfies the above five conditions will only reject sn .
It may be easy to check the following figure directly instead of a rigorous proof:
We start at the upper-left state. The first part is the starter, and the counter, then the consistent checker, the terminator, finally the add-one checker. All the arc with no terminal nodes point to the bottom-right state, which is an all time acceptor. Some of the edges are not labeled due to lack of spaces, but they can be recovered easily. A dash line represents a sequence ofn−1 states with n−2 edges.
We can (painfully) verify that the NFA rejectssn only, since it follows all the five rules above. So a (5n+12) -state NFA with |Σ|=5 has been constructed, which satisfies the requirement of the theorem.
If there's any unclearliness/problem with the construction, please leave a comment and I'll try to explain/fix it.
This question has been studied by Jeffrey O. Shallit et al., and indeed the optimal value off(n) is still open for |Σ|>1 . (As for unary language, see the comments in Tsuyoshi's answer)
In page 46-51 of his talk on universality, he provided a construction such that:
Thus the optimal value forf(n) is somewhere between 2n/75 and 2n . I'm not sure if the result by Shallit has been improved in recent years.
quelle