Согласно Википедии , для любого регулярного языка существуют константы и полиномы такие что для каждого число слов длины в удовлетворяет уравнению
.
Язык является регулярным (ему соответствует ). если n четно, а противном случае.
Тем не менее, я не могу найти и (которые должны существовать по вышеуказанному). Так как должен быть дифференцируемым и не постоянным, он должен как-то вести себя как волна, и я не могу понять, как вы можете сделать это с помощью полиномов и экспоненциальных функций, не заканчивая бесконечным числом слагаемых, как в расширение Тейлора. Кто-нибудь может просветить меня?
formal-languages
regular-languages
combinatorics
word-combinatorics
Алекс тен Бринк
источник
источник
Ответы:
Для вашего языка, вы можете взять , λ 0 = 1 , р 1 ( х ) = 1 / 2 , λ 1 = - 1 , и р я ( х ) = λ я = 0 для я > 1 ? В статье Википедии ничего не говорится о том, что коэффициенты являются либо положительными, либо целыми. Сумма за мой выборp0(x)=1/2 λ0=1 p1(x)=1/2 λ1=−1 pi(x)=λi=0 i>1
которая кажется 1 для четного и 0 для нечетного n . Действительно, доказательство по индукции кажется простым.n n
источник
@ Patrick87 дает отличный ответ для вашего конкретного случая, я подумал, что дам совет, как найти в более общем случае любого языка L, который может быть представлен неприводимым DFA (т. Е. Если это возможно) попасть в любой штат из любого штата). Обратите внимание, что ваш язык относится к этому типу.sL(n) L
Доказательство теоремы для неприводимых ДФА
Пусть будет матрицей переходов вашего DFA для m- состояния, поскольку она неприводима, матрица нормальна и имеет полное собственное основание | λ 1 ⟩ . , , | λ м ⟩ . Пусть | ⟩ Быть принимают вектор: т.е. ⟨ я | ⟩ Является 1 , если я это принимает состояние, и 0 в противном случае. WLOG предполагает, что | 1 ⟩ начальное состояние, а так как у нас есть полный собственный базис, мы знаем , что Х 1 ⟩ + . , ,D m |λ1⟩...|λm⟩ |A⟩ ⟨i|A⟩ i |1⟩ для некоторых коэффициентов гр 1 . , , с м (заметимчто с я = ⟨ А , я | я ⟩ ).|1⟩=c1|λ1⟩+...+cm|λm⟩ c1...cm ci=⟨λ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). SinceD 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:
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 ofD 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 languageL we can select the DFA with transition matrix:
and accept vector:
источник
Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrixA and two vectors x,y such that
Jordan's theorem states that over the complex numbers,A is similar to a matrix with blocks of one of the forms
Summarizing, every entry inAn is either of the form (nk)λn−k or of the form [n=k] , and we deduce that
источник