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

15

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 .λ 1 ,Lp 1 ( x ) ,λ1,,λkn s L ( n ) n L s L ( n ) = p 1 ( n ) λ n 1 + + p k ( n ) λ n kp1(x),,pk(x)nsL(n)nLsL(n)=p1(n)λ1n++pk(n)λkn

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.C NλCN

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)

Gilles 'SO - hör auf böse zu sein'
quelle
3
Eine Skizze eines Beweises ist hier
Artem Kaznatcheev
3
@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'
1
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'
1
@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:

10

Wenn eine reguläre Sprache , betrachten Sie einige DFA als L akzeptierend , lassen Sie A seine Übertragungsmatrix sein ( A i j ist die Anzahl der Kanten, die von Zustand i zu Zustand j führen ), lassen Sie x den charakteristischen Vektor des Anfangszustands sein und lassen Sie y sei der charakteristische Vektor der akzeptierenden Zustände. Dann ist s L ( n ) = x T A n y .LLAAijijxy

sL(n)=xTAny.

Jordan-Theorem besagt , dass über die komplexen Zahlen, eine Matrix mit Blöcken von einem der Formen ähnlich ist ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λ 1 0 0 0 λ 1 0 0 0 λ ) , Wenn λ 0 , dann ist das nA

(λ),(λ10λ),(λ100λ100λ),(λ1000λ1000λ1000λ),
λ0nDie 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.B=λ+NNλNBn=(λ+n)N=λn+nλn-1N+(n
(λn),(λnnλn10λn),(λnnλn1(n2)λn20λnnλn100λn),(λnnλn1(n2)λn2(n3)λn30λnnλn1(n2)λn200λnnλn1000λn),
B=λ+NNλpendelt mit ), Wenn , ist der Block nullpotent und wir erhalten die folgenden Matrizen (die Notation ist wenn und sonst ): N
Bn=(λ+n)N=λn+nλn1N+(n2)λn2N2+.
λ=0[n=k]1n=k0
([n=0]),([n=0][n=1]0[n=0]),([n=0][n=1][n=2]0[n=0][n=1]00[n=0]),([n=0][n=1][n=2][n=3]0[n=0][n=1][n=2]00[n=0][n=1]000[n=0])

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.An(nk)λnk[n=k]

sL(n)=ipi(n)λin+jcj[n=j],
λi,cjpin
sL(n)=ipi(n)λin.

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 giltsL(n)λiλ1

sL(n)=p1(n)λ1n(1+o(1)).
λdsLndλ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 , dp0,,pd1λ0,,λd1
sL(n)=npn(modd)λn(modd)n(1+o(1)).
Yuval Filmus
quelle
8

Sei eine reguläre Sprache undLΣ

L(z)=n0|Ln|zn

seine Erzeugungsfunktion , wobei und damit .Ln=LΣn|Ln|=sL(n)

Es ist bekannt , daß ist rational , alsoL(z)

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 .L L ( z )P,QLL(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 ).| L n | ( | L n | ) n NQ|Ln|(|Ln|)nN

Raphael
quelle
Es ist nicht klar, wie Ihre Antwort die Frage beantwortet. Was ist ? Ln
Dave Clarke
1
@Gilles Analytic Combinatorics , die Bücher von Eilenberg, das Buch von Berstel, Reutenauer
uli
1
@Gilles automaten -theoretische Aspekte formaler
uli
1
Q(z)=1kn0
1
@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