Zählen der Anzahl der von einer azyklischen NFA akzeptierten Wörter

Sei eine azyklische NFA.$M$

Da azyklisch ist, ist endlich.L ( M $M$$L(M)$

Können wir berechnenin Polynomzeit?$|L(M)|$

Wenn nicht, können wir es annähern?

Beachten Sie, dass die Anzahl der Wörter nicht mit der Anzahl der akzeptierenden Pfade in , was leicht berechenbar ist.$M$

Lassen Sie mich einen offensichtlichen Ansatz erwähnen, der nicht funktioniert: Konvertieren Sie den NFA in einen DFA (der auch azyklisch sein wird) und zählen Sie dann die Anzahl der akzeptierenden Pfade im DFA. Dies führt nicht zu einem Polynom-Zeit-Algorithmus, da die Konvertierung eine exponentielle Vergrößerung der Größe des DFA verursachen kann.

Hier ist ein Ansatz, von dem ich erwarte, dass er Ihnen eine Multiplikator-Faktor-Näherung mit polynomieller Laufzeit liefert.

Sei eine reguläre Sprache, die eine Teilmenge von , z. B. . Wir werden versuchen, die ungefähre Größe von zu berechnen .{ 0 , 1 } n L = L ( M ) ∩ { 0 , 1 } n$L$$\{0,1\}^n$$L=L(M) \cap \{0,1\}^n$$L$

Auf hohem Niveau ist unser Ansatz zur Annäherung anwird ungefähr so ​​aussehen:$|L|$

1. Wählen Sie einen Bruch , wobei .0 < p < $p$$0<p<1$

2. Wählen Sie eine reguläre Sprache , so dass, grob gesprochen, ist eine zufällige Teilmenge von der Größe etwa (dh ).R { 0 , 1 } n p 2 n | R | ≈ p 2 $R$$R$$\{0,1\}^n$$p2^n$$|R|\approx p2^n$

3. Überprüfen Sie, ob nicht leer ist. Beachten Sie, dass diese Prüfung in Polynomzeit durchgeführt werden kann.$L \cap R$

Führen Sie die Schritte 1 bis 3 wiederholt für verschiedene Werte von . Dies gibt Ihnen einige Informationen, mit denen Sie approximieren können .| L $p$$|L|$

Insbesondere wenn , dann würden wir erwarten$|L|=m$

Wenn Sie also zufällig wählen und die Schritte 1 bis 3 einige Male wiederholen, sollten Sie in etwa 37% der Fälle mit einer leeren Kreuzung rechnen. Wenn Sie eine leere Kreuzung deutlich häufiger sehen, erhöhen Sie und versuchen Sie es erneut. Wenn Sie eine leere Kreuzung deutlich seltener sehen, können Sie verringern und es erneut versuchen.$p=1/m$$p$$p$

Auf diese Weise sollten Sie mit einer binären Suche in der Lage sein, zu approximieren innerhalb eines multiplikativen Approximationsfaktors.$|L|$

Sie müssen noch einen Weg wählen, um zu wählen, damit es regelmäßig ist, sich aber auch wie eine zufällige Teilmenge verhält. Es gibt viele Möglichkeiten, aber ein guter Weg könnte darin bestehen, einen zufälligen 2-universellen Hash zu wählen , wähle zufällig und lasse . Wenn Sie Sie eine zufällige Menge von ungefähr der richtigen Größe. Da 2-universell ist, sollte die gesamte oben genannte Mathematik ordnungsgemäß funktionieren.$R$$h:\{0,1\}^m \to \{0,1,2,\dots,k-1\}$$y \in \{0,1,\dots,k-1\}$$R=\{x \in \{0,1\}^n : h(x)=y\}$$k=\lceil 1/p \rceil$$R$$h$

Dies sollte Ihr Problem für den Fall lösen, dass alle Zeichenfolgen in der NFA dieselbe Länge haben, z . B. . Wenn sie unterschiedliche Längen haben, können Sie jede mögliche Länge separat behandeln. Da azyklisch ist, entspricht die maximale Länge eines Strings in höchstens der Anzahl der Zustände in , wodurch die Laufzeit nicht zu stark erhöht wird.$n$$M$$L(M)$$M$

(Diese Konstruktion könnte Sie an den Satz von Vazirani-Vazirani über eindeutigen SAT erinnern.)

Angenommen, Sie können in Polynomzeit die Anzahl der Wörter einer Sprache zählen, die von einer azyklischen NFA angegeben wird. In diesem Fall können Sie unter Berücksichtigung von zwei azyklischen NFAs und in Polynomzeit den Kardinal (bzw. ) der Sprache von (bzw. ) berechnen . Durch ein direktes Produkt (Erhaltung der Azyklizität) können Sie auch in Polynomzeit den Kardinal des Schnittpunkts dieser beiden Sprachen berechnen . Die beiden Automaten akzeptieren dieselbe Sprache, wenn . Daher können Sie die Gleichheit zweier endlicher Sprachen testen, die von azyklischen Automaten im Polynom gegeben werden, was als NP-vollständiges Problem bekannt ist. Also, es sei denn,$A_1$$A_2$$n_1$$n_2$$A_1$$A_2$$n_3$$n_1=n_2=n_3$$P=NP$können Sie Ihr Problem nicht in Polynomzeit lösen.