Anzahl der Wörter in der regulären Sprache

Laut Wikipedia existieren für jede reguläre Sprache $L$ Konstanten $\lambda_1,\ldots,\lambda_k$ und Polynome $p_1(x),\ldots,p_k(x)$ so dass für jedes $n$ die Anzahl $s_L(n)$ von Wörtern der Länge gilt $n$ in $L$ erfüllt die Gleichung

$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$ .

Die Sprache $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ ist regulär ( $(00)^*$ passt dazu). $s_L(n) = 1$ wenn n gerade ist, und wenn $s_L(n) = 0$nicht.

Ich kann jedoch nicht die $\lambda_i$ und $p_i$ (die nach dem oben Gesagten existieren müssen). Da $s_L(n)$ differenzierbar und nicht konstant sein muss, muss es sich irgendwie wie eine Welle verhalten, und ich kann nicht sehen, wie man das möglicherweise mit Polynomen und Exponentialfunktionen machen kann, ohne eine unendliche Anzahl von Summanden wie zu erhalten in einer Taylor-Erweiterung. Kann mich jemand aufklären?

Für Ihre Sprache, können Sie nehmen , λ 0 = 1 , p 1 ( x ) = 1 / 2 , λ 1 = - 1 und p i ( x ) = λ i = 0 für i > 1 ? Der Wikipedia-Artikel sagt nichts darüber aus, dass die Koeffizienten entweder positiv oder ganzzahlig sind. Die Summe für meine Entscheidungen ist$p_0(x) = 1/2$$\lambda_0 = 1$$p_1(x) = 1/2$$\lambda_1 = -1$$p_i(x) = \lambda_i = 0$$i > 1$

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

Dies scheint 1 für gerade und 0 für ungerade n zu sein . In der Tat scheint ein Beweis durch Induktion einfach zu sein.$n$$n$

@ Patrick87 gibt eine großartige Antwort auf Ihren speziellen Fall. Ich dachte, ich würde einen Tipp geben, wie man im allgemeineren Fall jeder Sprache L findet, die durch einen irreduziblen DFA dargestellt werden kann (dh wenn es möglich ist) aus jedem Staat in jeden Staat gelangen). Beachten Sie, dass Ihre Sprache von diesem Typ ist.$s_L(n)$$L$

---

Beweis des Theorems für irreduzible DFAs

Lassen Sie die Übergangsmatrix Ihres sein m -state DFA, da es nicht reduzierbar ist, die Matrix ist normal und hat eine vollständige Eigenbasis | λ 1 ⟩ . . . | λ m ⟩ . Lassen | Ein ⟩ sein das akzeptieren Vektor: dh ⟨ i | A ⟩ ist 1 , wenn i ein Zustand annehmen wird, und 0 sonst. WLOG nehme an, dass | 1 ⟩ ist der Anfangszustand, und da wir eine komplette Eigenbasis haben, wissen wir, dass | 1 ⟩ = c 1 $D$$m$$|\lambda_1\rangle ... |\lambda_m\rangle$$|A\rangle$$\langle i | A \rangle$$i$$|1\rangle$ für einige Koeffizienten c 1 . . . c m (beachtendass c i = ⟨ & lgr; i | i ⟩ ).$|1\rangle = c_1|\lambda_1\rangle + ... + c_m|\lambda_m\rangle$$c_1 ... c_m$$c_i = \langle \lambda_i | i \rangle$

Nun können wir einen eingeschränkten Fall des Theorems in der Frage beweisen (beschränkt auf irreduzible DFAs; als Übung diesen Beweis auf den gesamten Theorem verallgemeinern). Da ist die Übergangsmatrix D | 1 ⟩ der Vektor der Zustände erreichbar , nachdem ein beliebiges Zeichen lesen, D 2 | 1 ⟩ ist das gleiche für zwei Zeichen usw. Bei einem Vektor | x ⟩ , ⟨ A | x ⟩ ist einfach die Summe der Komponenten | x ⟩ , die Zustände annehmen. Somit:$D$$D|1\rangle$$D^2|1\rangle$$|x\rangle$$\langle A|x\rangle$$|x\rangle$

$$\begin{align} s_L(n) & = \langle A |D^n| 1 \rangle \\ & =\langle A | D^n (c_1 |\lambda_1\rangle ... c_m |\lambda_m\rangle) \\ & = c_1 \lambda_1^n \langle A | \lambda_1 \rangle + ... + c_m \lambda_m^n \langle A | \lambda_m \rangle \\ & = \langle A | \lambda_1 \rangle\langle\lambda_1|1\rangle \lambda_1^n + ... + \langle A | \lambda_m \rangle\langle \lambda_m | 1 \rangle \lambda_m^n \\ & = p_1\lambda_1^n + ... + p_m \lambda_m^m \end{align}$$

Nun wissen wir, dass für einen irreduziblen DFA im m-Zustand sind Polynome nullter Ordnung (dh Konstanten), die von DFA und λ 1 abhängen . . . λ m sind Eigenwerte der Übergangsmatrix.$p_1 ... p_m$$\lambda_1 ... \lambda_m$

Allgemeiner Hinweis

Wenn Sie dieses Theorem für beliebige DFA beweisen wollen, müssen Sie die Schur-Zerlegung von und dann werden aufgrund der nullpotenten Terme Polynome ungleich null Grad auftauchen. Es ist immer noch aufschlussreich, dies zu tun, da Sie den maximalen Grad der Polynome einschränken können. Sie finden auch eine Beziehung zwischen der Komplexität der Polynome und der Anzahl der λs .$D$$\lambda$

---

Bewerbung auf konkrete Fragestellung

Für Ihre Sprache wir die DFA mit Übergangsmatrix auswählen:$L$

$$D = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

und akzeptiere vector:

$$A = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$

Finden Sie die Eigenvektoren und ihre Eigenwerte mit | λ 1 ⟩ = $\lambda_1 = 1$undλ2=-1mit| λ2⟩=$| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$$\lambda_2 = -1$. Wir können diese verwendenum zu findenp1=1/2undp2=1/2. Uns zu geben:$| \lambda_2 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$$p_1 = 1/2$$p_2 = 1/2$

$$s_L(n) = \frac{1}{2} + \frac{1}{2}(-1)^n$$

Weiter Artems Antwort, hier ist ein Beweis für die allgemeine Darstellung. Wie Artem zeigt, gibt es eine ganzzahlige Matrix und zwei Vektoren x , y, so dass s L ( n ) = x T A n y ist . (Der Vektor x ist der charakteristische Vektor des Startzustands, der Vektor y ist der charakteristische Vektor aller akzeptierenden Zustände und A i j ist gleich der Anzahl der Übergänge von Zustand i zu Zustand j in einem DFA für die Sprache.)$A$$x,y$

$$s_L(n) = x^T A^n y.$$ $x$$y$$A_{ij}$$i$$j$

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

$$\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$$ $\lambda \neq 0$$n$Die Potenzen dieser Blöcke sind Hier istwie wir in diesen Formeln bekommen: den Block als schreibenB=λ+N. Aufeinanderfolgende Potenzen vonNsind aufeinanderfolgende sekundäre Diagonalen der Matrix. Unter Verwendung des Binomialsatzes (unter Verwendung der Tatsache, dassλmitNkommutiert) ist Bn=(λ+n)N= $$\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 = \lambda + N$$N$$\lambda$$N$ Wennλ=0 ist, ist der Block nicht potent und wir erhalten die folgenden Matrizen (die Notation[n=k]ist1,wennn=kundsonst0): ( [ n = 0 ] ) , ( [ n = 0 ] [ n = 1 ] 0 [ n = 0 ] ),( [ n = 0 $$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$$ $\lambda = 0$$[n = k]$$1$$n=k$$0$ $$\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}$$

$A^n$$\binom{n}{k} \lambda^{n-k}$$[n=k]$

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