Anzahl der Wörter einer bestimmten Länge in einer regulären Sprache

Gibt es eine algebraische Charakterisierung der Anzahl der Wörter einer bestimmten Länge in einer regulären Sprache?

Wikipedia gibt ein etwas ungenaues Ergebnis an:

Für jede reguläre Sprache existieren Konstanten und Polynome so dass für jedes die Anzahl von gilt Wörter der Länge in erfüllen die Gleichung . $L$ $\lambda_1,\,\ldots,\,\lambda_k$ $p_1(x),\,\ldots,\,p_k(x)$ $n$ $s_L(n)$ $n$ $L$ $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$

Es wird nicht angegeben, in welchem Raum die leben ( , nehme ich an) und ob die Funktion nichtnegative ganzzahlige Werte für . Ich hätte gerne eine genaue Aussage und eine Skizze oder einen Hinweis für den Beweis. $\lambda$ $\mathbb{C}$ $\mathbb{N}$

Bonusfrage: Ist das Umgekehrte wahr, dh gibt es bei einer Funktion dieser Form immer eine reguläre Sprache, deren Anzahl der Wörter pro Länge dieser Funktion entspricht?

_{Diese Frage verallgemeinert die Anzahl der Wörter in der regulären Sprache $(00)^*$}

formal-languages regular-languages word-combinatorics Gilles 'SO - hör auf böse zu sein'
quelle

Eine Skizze eines Beweises ist hier

Artem Kaznatcheev

@ArtemKaznatcheev Interessant, danke. Würden Sie in Betracht ziehen, Ihre Antwort auf diese Frage zu verschieben, die besser passt?

Gilles 'SO- hör auf böse zu sein'

Ich halte diese Frage für etwas überflüssig (wenn auch allgemeiner). Die Verallgemeinerung meines Ansatzes zum Beweis ist ein wenig haarig, aber ich werde mich nach dem Abendessen umsehen.

Artem Kaznatcheev

@ArtemKaznatcheev Danke. Ich hatte Probleme mit dem zweiten Teil Ihrer Antwort, der sich auf reduzierbare DFAs erstreckt.

Gilles 'SO- hör auf böse zu sein'

@vzn Es ist eine klassische Tatsache, dass die Erzeugungsfunktion der Anzahl der Wörter in einer regulären Sprache rational ist, was unmittelbar die Formel des OP (in ihrer korrekten Form) impliziert. Der schwierige Teil ist das Herausziehen der Asymptotika. Einzelheiten können Sie (zum Beispiel) dem in meiner Antwort erwähnten Buch Analytic Combinatorics entnehmen.

Yuval Filmus

Antworten:

Wenn eine reguläre Sprache , betrachten Sie einige DFA als akzeptierend , lassen Sie seine Übertragungsmatrix sein ( ist die Anzahl der Kanten, die von Zustand zu Zustand ), lassen Sie den charakteristischen Vektor des Anfangszustands sein und lassen Sie sei der charakteristische Vektor der akzeptierenden Zustände. Dann ist $L$ $L$ $A$ $A_{ij}$ $i$ $j$ $x$ $y$

s_{L} (n) = x^{T} A^{n} y .

$s_L(n) = x^T A^n y.$

Jordan-Theorem besagt , dass über die komplexen Zahlen, eine Matrix mit Blöcken von einem der Formen ähnlich ist Wenn , dann ist das $A$

(\begin{matrix} λ \end{matrix}), (\begin{matrix} λ & 1 \\ 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 \\ 0 & λ & 1 \\ 0 & 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 & 0 \\ 0 & λ & 1 & 0 \\ 0 & 0 & λ & 1 \\ 0 & 0 & 0 & λ \end{matrix}), \dots

$\begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots$

λ \neq 0

$\lambda \neq 0$

n

$n$ Die Potenzen dieser Blöcke sind Hier ist , wie wir in diesen Formeln bekam: den Block als schreiben . Aufeinanderfolgende Potenzen von sind aufeinanderfolgende sekundäre Diagonalen der Matrix.

(\begin{matrix} λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} \\ 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} \\ 0 & λ^{n} & n λ^{n - 1} \\ 0 & 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} & (\binom{n}{3}) λ^{n - 3} \\ 0 & λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} \\ 0 & 0 & λ^{n} & n λ^{n - 1} \\ 0 & 0 & 0 & λ^{n} \end{matrix}), \dots

$\begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots$

B = λ + N

$B = \lambda + N$

N

$N$

λ

$\lambda$ pendelt mit ), Wenn , ist der Block nullpotent und wir erhalten die folgenden Matrizen (die Notation ist wenn und sonst ):

N

$N$

B^{n} = (λ + n)^{N} = λ^{n} + n λ^{n - 1} N + (\binom{n}{2}) λ^{n - 2} N^{2} + \dots .

$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$

λ = 0

$\lambda = 0$

[n = k]

$[n = k]$

1

$1$

n = k

$n=k$

0

$0$

(\begin{matrix} [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] \\ 0 & [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] & [n = 2] \\ 0 & [n = 0] & [n = 1] \\ 0 & 0 & [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] & [n = 2] & [n = 3] \\ 0 & [n = 0] & [n = 1] & [n = 2] \\ 0 & 0 & [n = 0] & [n = 1] \\ 0 & 0 & 0 & [n = 0] \end{matrix})

$\begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix}$

Zusammenfassend hat jeder Eintrag in entweder die Form oder die Form , und wir schließen daraus, dass für einige komplexe und komplexe Polynome . Insbesondere für die groß genug , um , Dies ist die genaue Angabe des Ergebnisses. $A^n$ $\binom{n}{k} \lambda^{n-k}$ $[n=k]$

s_{L} (n) = \sum_{i} p_{i} (n) λ_{i}^{n} + \sum_{j} c_{j} [n = j],

$s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j],$

λ_{i}, c_{j}

$\lambda_i,c_j$

p_{i}

$p_i$ $n$

s_{L} (n) = \sum_{i} p_{i} (n) λ_{i}^{n} .

$s_L(n) = \sum_i p_i(n) \lambda_i^n.$

Wir können weiterhin asymptotische Informationen über , aber dies ist überraschenderweise nicht trivial. Wenn es ein eindeutiges der größten Größe gibt, sagen wir , dann ist Komplizierter wird es, wenn es mehrere der größten Größenordnung gibt. Es kommt also vor, dass ihr Winkel rational sein muss (dh bis zur Größe sind sie Wurzeln der Einheit). Wenn die LCM der Nenner , dann wird die Asymptotik von sehr nach dem Rest von Modulo . Für einige dieser Reste gilt $s_L(n)$ $\lambda_i$ $\lambda_1$

s_{L} (n) = p_{1} (n) λ_{1}^{n} (1 + o (1)) .

$s_L(n) = p_1(n) \lambda_1^n (1 + o(1)).$

λ

$\lambda$

d

$d$

s_{L}

$s_L$

n

$n$

d

$d$

λ

$\lambda$ s mit der größten Größe werden gelöscht, und dann "fällt" die Asymptotik ab, und wir müssen diese Prozedur wiederholen. Der interessierte Leser kann die Details in Flajolet und Sedgewicks Analytic Combinatorics , Theorem V.3, nachlesen. Sie beweisen, dass für einige ganze Zahlen und Zahlen ,

d

$d$

p_{0}, \dots, p_{d - 1}

$p_0,\ldots,p_{d-1}$

λ_{0}, \dots, λ_{d - 1}

$\lambda_0,\ldots,\lambda_{d-1}$

s_{L} (n) = n^{p_{n (\mod d)}} λ_{n (\mod d)}^{n} (1 + o (1)) .

$s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)).$

Yuval Filmus
quelle

Sei eine reguläre Sprache und $L \subseteq \Sigma^*$

$\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$

seine Erzeugungsfunktion , wobei und damit . $L_n = L \cap \Sigma^n$ $|L_n|=s_L(n)$

Es ist bekannt , daß ist rational , also $L(z)$

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

mit Polynome; Dies ist am einfachsten zu sehen, wenn eine rechtslineare Grammatik für in ein (lineares!) Gleichungssystem übersetzt wird, dessen Lösung . $P,Q$ $L$ $L(z)$

Die Wurzeln von sind im Wesentlichen für, was zu dem auf Wikipedia angegebenen Formular führt. Dies hängt unmittelbar mit der Methode der charakteristischen Polynome zur Lösung von Wiederholungen zusammen (über die Wiederholung, die ). $Q$ $|L_n|$ $(|L_n|)_{n \in \mathbb{N}}$

Raphael
quelle

Es ist nicht klar, wie Ihre Antwort die Frage beantwortet. Was ist ?

L_{n}

$L_n$

Dave Clarke

@Gilles Analytic Combinatorics , die Bücher von Eilenberg, das Buch von Berstel, Reutenauer

uli

@Gilles automaten -theoretische Aspekte formaler

uli

Q (z) = 1

$Q(z)=1$

k \geq n_{0}

$k \geq n_0$

@Raphael Ja, mein Denken war ähnlich ... das scheint ein ziemlich schwerwiegender Mangel in der Darstellung des Theorems zu sein, wenn es nicht für endliche Sprachen gilt, da (a) endliche Sprachen regulär sind, (b) der Theorem impliziert, dass endliche Sprachen nicht regulär sind, und (c) es (im Allgemeinen) unentscheidbar ist, zu bestimmen, ob eine Sprache endlich ist ... Ich meine, Myhill-Nerode und das pumpfähige Lemma haben dieses Problem nicht; Sie arbeiten für endliche Sprachen.

Patrick87