Существует ли алгебраическая характеристика числа слов заданной длины в обычном языке?
Википедия приводит результат несколько неточно:
Для любого регулярного языка существуют константы и многочлены таким образом, что для каждого п числа s_L (п) из слова длины n в L удовлетворяют уравнению s_L (n) = p_1 (n) \ lambda_1 ^ n + \ dotsb + p_k (n) \ lambda_k ^ n .
Не указано, в каком пространстве живут ( я полагаю, ) и требуется, чтобы функция имела неотрицательные целочисленные значения по всем . Я хотел бы точное утверждение, и эскиз или ссылку для доказательства.
Дополнительный вопрос: верно ли обратное, то есть задана ли функция этой формы, всегда ли существует регулярный язык, число слов которого в длину равно этой функции?
Этот вопрос обобщает количество слов на обычном языке
источник
Ответы:
Для регулярного языка рассмотрим некоторый DFA, принимающий , пусть будет его матрицей переноса ( - это число ребер, ведущих из состояния в состояние ), пусть будет характеристическим вектором начального состояния, и пусть будет характерным вектором принимающих состояний. Тогда L A A i j i j x y s L ( n ) = x T A n y .L L A Aя ж я J Икс Y
Теорема Джордана утверждает, что по комплексным числам подобна матрице с блоками одной из форм Если , то Силы этих блоков ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λA λ≠0n( λ n ),( λ n n λ n - 1
Подводя итог, можно сказать, что каждая запись в имеет вид или форму , и мы что для некоторых комплексных и комплексных полиномов . В частности, при достаточно больших , Это точное утверждение результата.AN ( нК) λн - к [ п = к ]
Мы можем продолжить и получить асимптотическую информацию о , но это удивительно нетривиально. Если существует уникальный наибольшей величины, скажем, , то Все становится сложнее, когда есть несколько с наибольшей величиной. Так получилось, что их угол должен быть рациональным (т.е. с точностью до величины они являются корнями единства). Если LCM знаменателей равен , то асимптотика будет очень соответствовать остатку от по модулю . Для некоторых из этих остатков всеsL( н ) λя λ1
источник
Пусть обычный язык иL ⊆ Σ*
его производящая функция , где и т. д. .LN= L ∩ ΣN | LN| = сL( н )
Известно , что является рациональным , т.е.L ( z)
с полиномами; это легче всего увидеть, переведя линейно-правую грамматику для в (линейную!) систему уравнений, решением которой является .п, Q L L ( z)
Корни по существу ответственны за, что приводит к форме, указанной в Википедии. Это непосредственно связано с методом характеристических полиномов для решения повторений (через повторение, которое описывает ).Q | LN| ( | LN| )n ∈ N
источник