Zählen von Wörtern, die von einer normalen Grammatik akzeptiert werden

Wie kann bei einer vorgegebenen regulären Sprache (NFA, DFA, Grammatik oder Regex) die Anzahl der akzeptierten Wörter in einer bestimmten Sprache gezählt werden? Sowohl "mit genau n Buchstaben" als auch "mit höchstens n Buchstaben" sind von Interesse.

Margareta Ackerman hat zwei Artikel zum Thema der Aufzählung von Wörtern, die von einer NFA akzeptiert wurden, aber ich konnte sie nicht ändern, um effizient zu zählen.

Es scheint, dass die Einschränkung regulärer Sprachen das Zählen relativ einfach machen sollte - ich erwarte fast eine Formel mehr als einen Algorithmus. Leider haben meine Suchanfragen bisher nichts ergeben, daher muss ich die falschen Begriffe verwenden.

Für einen DFA, in dem der Anfangszustand ist der Zustand , die Anzahl der Worte der Länge k , die im Zustand am Ende i ist A k [ 0 , i ] , wobei A die Übertragungsmatrix des DFA ist (eine Matrix , in der die Zahl in Zeile i und Spalte j ist die Anzahl der verschiedenen Eingabesymbole, die einen Übergang vom Zustand i zum Zustand j bewirken . So können Sie zählen, Wörter mit einer Länge von genau k einfach zu akzeptieren , auch wenn $0$$k$$i$$A^k[0,i]$$A$$i$$j$$i$$j$$k$$k$ ist mäßig groß, indem nur eine Matrixleistung berechnet und die Einträge hinzugefügt werden, die den akzeptierenden Zuständen entsprechen.

Dasselbe gilt für die Annahme von Wörtern mit einer Länge von höchstens und einer geringfügig anderen Matrix. Fügen Sie eine zusätzliche Zeile und Spalte der Matrix hinzu, und zwar eine in der Zelle, die sowohl in der Zeile als auch in der Spalte enthalten ist, eine in der neuen Zeile und Spalte des Anfangszustands sowie eine Null in allen anderen Zellen. Diese Änderung der Matrix hat zur Folge, dass dem Ausgangszustand bei jeder Leistung ein weiterer Pfad hinzugefügt wird.$k$

Dies funktioniert nicht für NFAs. Ich vermute, das Beste ist, einfach in einen DFA zu konvertieren und dann den Matrix-Powering-Algorithmus anzuwenden.

Let mit Startzustand ein (nichtdeterministischen) finite Automatisierungs seine Q 1 , Q F ⊆ Q und δ ⊆ Q × Σ × Q .$A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$$q_1$$Q_F \subseteq Q$$\delta \subseteq Q\times\Sigma\times Q$

Sei die Erzeugungsfunktion für alle Wörter, die ab q i akzeptiert werden können , also der n- te Koeffizient seiner Reihenexpansion [ z n ] Q i = | { w ∣ | w | = n ∧ w  von q i } | akzeptiert .$Q_i(z)$$q_i$$n$$[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$

Deutlich:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(z)$

Lösen Sie das resultierende (lineare) Gleichungssystem für (mit Mathematica oder einem ähnlichen Werkzeug). Dann ist [ z n ] Q 1 die gewünschte Größe.$Q_1$$[z^n]Q_1$

Dies geht auf eine von Chomsky und Schützenberger (1963) für Grammatiken eingeführte Technik zurück; es kann leicht auf endliche Automaten übertragen werden.

Bearbeiten: Wenn Sie Übergänge berücksichtigen möchten , lassen Sie Faktor x in der Summe für den entsprechenden Übergang weg . Wenn Sie „komprimieren“ Kanten Similiarly haben, das heißt , statt dem Symbol a ∈ & Sigma; ein Wort w ∈ & Sigma; k auf einem Übergang, ersetzen x mit x k .$\varepsilon$$x$$a \in \Sigma$$w \in \Sigma^k$$x$$x^k$

Ich denke, dass dies ein schwieriges Zählproblem ist, siehe dieses Papier: Das Zählen der Größe regulärer Sequenzen mit der angegebenen Länge ist # P-vollständig: S. Kannan, Z. Sweedyk und SR Mahaney. Zählen und zufälliges Erzeugen von Strings in regulären Sprachen. In ACM-SIAM Symposium on Discrete Algorithms (SODA), S. 551–557, 1995.

$\#\mathsf{NC}^1$