Количество слов в обычном языке

17

Согласно Википедии , для любого регулярного языка существуют константы и полиномы такие что для каждого число слов длины в удовлетворяет уравнениюLλ1,,λkp1(x),,pk(x)nsL(n)nL

sL(n)=p1(n)λ1n++pk(n)λkn .

Язык является регулярным (ему соответствует ). если n четно, а противном случае.L={02nnN}(00)sL(n)=1sL(n)=0

Тем не менее, я не могу найти и (которые должны существовать по вышеуказанному). Так как должен быть дифференцируемым и не постоянным, он должен как-то вести себя как волна, и я не могу понять, как вы можете сделать это с помощью полиномов и экспоненциальных функций, не заканчивая бесконечным числом слагаемых, как в расширение Тейлора. Кто-нибудь может просветить меня?λipisL(n)

Алекс тен Бринк
источник
Вы знаете название этой теоремы?
Артем Казнатчеев
@ArtemKaznatcheev: нет, не знаю. Википедия, к сожалению, также не дает ссылки :(
Алекс тен Бринк
В более общем смысле: количество слов заданной длины на обычном языке
Жиль "ТАК, перестань быть злым"

Ответы:

14

Для вашего языка, вы можете взять , λ 0 = 1 , р 1 ( х ) = 1 / 2 , λ 1 = - 1 , и р я ( х ) = λ я = 0 для я > 1 ? В статье Википедии ничего не говорится о том, что коэффициенты являются либо положительными, либо целыми. Сумма за мой выборp0(x)=1/2λ0=1p1(x)=1/2λ1=1pi(x)=λi=0i>1

1/2+1/2(1)n=1/2(1+(1)n)

которая кажется 1 для четного и 0 для нечетного n . Действительно, доказательство по индукции кажется простым.nn

Patrick87
источник
Ах да, конечно, я забыл о знакопеременных знаках минус. Буду поднимать голос после того, как день закончится - я достиг предела голосования.
Алекс тен Бринк
Никакой индукции не требуется для этого требования.
Рафаэль
@Raphael Правда, но опять же, это только делает мое утверждение еще более точным.
Patrick87
11

@ Patrick87 дает отличный ответ для вашего конкретного случая, я подумал, что дам совет, как найти в более общем случае любого языка L, который может быть представлен неприводимым DFA (т. Е. Если это возможно) попасть в любой штат из любого штата). Обратите внимание, что ваш язык относится к этому типу.sL(n)L


Доказательство теоремы для неприводимых ДФА

Пусть будет матрицей переходов вашего DFA для m- состояния, поскольку она неприводима, матрица нормальна и имеет полное собственное основание | λ 1. , , | λ м . Пусть | Быть принимают вектор: т.е. я | Является 1 , если я это принимает состояние, и 0 в противном случае. WLOG предполагает, что | 1 начальное состояние, а так как у нас есть полный собственный базис, мы знаем , что Х 1+ . , ,Dm|λ1...|λm|Ai|Ai|1 для некоторых коэффициентов гр 1 . , , с м (заметимчто с я = А , я | я ).|1=c1|λ1+...+cm|λmc1...cmci=λi|i

Now we can prove a restricted case of the theorem in the question (restricted to irreducible DFAs; as an exercise generalize this proof to the whole theorem). Since D is the transition matrix D|1 is the vector of states reachable after reading any one character, D2|1 is the same for two characters, etc. Given a vector |x, A|x is simply the sum of the components of |x that are accept states. Thus:

sL(n)=A|Dn|1=A|Dn(c1|λ1...cm|λm)=c1λ1nA|λ1+...+cmλmnA|λm=A|λ1λ1|1λ1n+...+A|λmλm|1λmn=p1λ1n+...+pmλmm

Now we know that for an irreducible m-state DFA, p1...pm will be zero order polynomials (i.e. constants) that depends on the DFA and λ1...λm will be eigenvalues of the transition matrix.

Generality note

If you want to prove this theorem for arbitrary DFA, then you will need to look at the Schur decomposition of D and then polynomials of non-zero degree will pop up because of the nilpotent terms. It is still enlightening to do this, since it will let you bound the max degree of the polynomials. You will also find a relationship between how complicated the polynomials are and how many λs you will have.


Application to specific question

For your language L we can select the DFA with transition matrix:

D=(0110)

and accept vector:

A=(10)

λ1=1|λ1=12(11) and λ2=1 with |λ2=12(11). We can use this to find p1=1/2 and p2=1/2. To give us:

sL(n)=12+12(1)n
Artem Kaznatcheev
источник
Maybe post this here?
Raphael
@Raphael that was asked while I was figuring out the proof and typing up my answer, so I did not know about it when I asked.
Artem Kaznatcheev
6

Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrix A and two vectors x,y such that

sL(n)=xTAny.
(The vector x is the characteristic vector of the start state, the vector y is the characteristic vector of all accepting state, and Aij is equal to the number of transitions from state i to state j in a DFA for the language.)

Jordan's theorem states that over the complex numbers, A is similar to a matrix with blocks of one of the forms

(λ),(λ10λ),(λ100λ100λ),(λ1000λ1000λ1000λ),
If λ0, then the nth powers of these blocks are
(λn),(λnnλn10λn),(λnnλn1(n2)λn20λnnλn100λn),(λnnλn1(n2)λn2(n3)λn30λnnλn1(n2)λn200λnnλn1000λn),
Here's how we got to these formulas: write the block as B=λ+N. Successive powers of N are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that λ commutes with N),
Bn=(λ+n)N=λn+nλn1N+(n2)λn2N2+.
When λ=0, the block is nilpotent, and we get the following matrices (the notation [n=k] is 1 if n=k and 0 otherwise):
([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])

Summarizing, every entry in An is either of the form (nk)λnk or of the form [n=k], and we deduce that

sL(n)=ipi(n)λi(n)+jcj[n=j],
for some complex λi,cj and complex polynomials pi. In particular, for large enough n,
sL(n)=ipi(n)λi(n).
Yuval Filmus
источник
Thank you for the general treatment! You should consider combining your answer with mine and posting it as a full answer to this question. I think it would be more helpful than the current answer there.
Artem Kaznatcheev