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

15

Существует ли алгебраическая характеристика числа слов заданной длины в обычном языке?

Википедия приводит результат несколько неточно:

Для любого регулярного языка существуют константы и многочлены таким образом, что для каждого п числа s_L (п) из слова длины n в L удовлетворяют уравнению s_L (n) = p_1 (n) \ lambda_1 ^ n + \ dotsb + p_k (n) \ lambda_k ^ n .Lλ1,...,λКп1(Икс),...,пК(Икс)NsL(N)NLsL(N)знак равноп1(N)λ1N++пК(N)λКN

Не указано, в каком пространстве живут λ ( я полагаю, С ) и требуется, чтобы функция имела неотрицательные целочисленные значения по всем N . Я хотел бы точное утверждение, и эскиз или ссылку для доказательства.

Дополнительный вопрос: верно ли обратное, то есть задана ли функция этой формы, всегда ли существует регулярный язык, число слов которого в длину равно этой функции?

Этот вопрос обобщает количество слов на обычном языке (00)*

Жиль "ТАК - перестань быть злым"
источник
3
Эскиз доказательства здесь
Артем Казнатчеев
3
@ArtemKaznatcheev Интересно, спасибо. Не могли бы вы переместить свой ответ на этот вопрос, который подходит лучше?
Жиль "ТАК - перестань быть злым"
1
Я чувствую, что этот вопрос немного излишний (хотя и более общий). Обобщать мой подход к доказательству немного сложно, но я посмотрю после обеда.
Артем Казнатчеев
@ArtemKaznatcheev Спасибо. У меня были проблемы со второй частью вашего ответа, распространяющейся на сокращаемые DFA.
Жиль "ТАК - прекрати быть злым"
1
@vzn Классический факт, что производящая функция числа слов в регулярном языке рациональна, что сразу подразумевает формулу ОП (в ее правильном виде). Трудной частью является извлечение асимптотики. Для подробностей вы можете проверить (например) книгу Analytic Combinatorics, упомянутую в моем ответе.
Юваль Фильмус

Ответы:

10

Для регулярного языка рассмотрим некоторый DFA, принимающий , пусть будет его матрицей переноса ( - это число ребер, ведущих из состояния в состояние ), пусть будет характеристическим вектором начального состояния, и пусть будет характерным вектором принимающих состояний. Тогда L A A i j i j x y s L ( n ) = x T A n y .LLAAяJяJИксY

sL(N)знак равноИксTANY,

Теорема Джордана утверждает, что по комплексным числам подобна матрице с блоками одной из форм Если , то Силы этих блоков ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λAλ0n( λ n ),( λ n n λ n - 1

(λ),(λ10λ),(λ100λ100λ),(λ1000λ1000λ1000λ),...
λ0N
(λN),(λNNλN-10λN),(λNNλN-1(N2)λN-20λNNλN-100λN),(λNNλN-1(N2)λN-2(N3)λN-30λNNλN-1(N2)λN-200λNNλN-1000λN),...
Вот как мы получили по этим формулам: записать блок как . Последовательные степени являются последовательными вторичными диагоналями матрицы.N λ N B n = ( λ + n ) N = λ n + n λ n - 1 N + ( nВзнак равноλ+NNλN
ВNзнак равно(λ+N)Nзнак равноλN+NλN-1N+(N2)λN-2N2+,
Когда , блок является нильпотентным, и мы получаем следующие матрицы (запись равна если и противном случае): [ n = k ] 1 n = k 0 ( [ n = 0 ] ) , ] [ n = 1 ] 0 0 [ n = 0 ] ) , ( [ n =λзнак равно0[Nзнак равноК]1Nзнак равноК0
([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])

Подводя итог, можно сказать, что каждая запись в имеет вид или форму , и мы что для некоторых комплексных и комплексных полиномов . В частности, при достаточно больших , Это точное утверждение результата.AN(NК)λN-К[Nзнак равноК]

sL(N)знак равноΣяпя(N)λяN+ΣJсJ[Nзнак равноJ],
λя,сJпяN
sL(N)знак равноΣяпя(N)λяN,

Мы можем продолжить и получить асимптотическую информацию о , но это удивительно нетривиально. Если существует уникальный наибольшей величины, скажем, , то Все становится сложнее, когда есть несколько с наибольшей величиной. Так получилось, что их угол должен быть рациональным (т.е. с точностью до величины они являются корнями единства). Если LCM знаменателей равен , то асимптотика будет очень соответствовать остатку от по модулю . Для некоторых из этих остатков всеsL(N)λяλ1

sL(N)знак равноп1(N)λ1N(1+о(1)),
λdsLNdλs наибольшей величины отменяются, и затем асимптотика «падает», и мы должны повторить эту процедуру. Заинтересованный читатель может проверить подробности в « Аналитической комбинаторике Флайолета и Седжвика» , теорема V.3. Они доказывают, что для некоторых целые числа и действительные числа , dп0,...,пd-1λ0,...,λd-1
sL(N)знак равноNпN(модификацияd)λN(модификацияd)N(1+о(1)),
Юваль Фильмус
источник
8

Пусть обычный язык иLΣ*

L(Z)знак равноΣN0|LN|ZN

его производящая функция , где и т. д. .LNзнак равноLΣN|LN|знак равноsL(N)

Известно , что является рациональным , т.е.L(Z)

п(Z)Q(Z)

с полиномами; это легче всего увидеть, переведя линейно-правую грамматику для в (линейную!) систему уравнений, решением которой является .п,QLL(Z)

Корни по существу ответственны за, что приводит к форме, указанной в Википедии. Это непосредственно связано с методом характеристических полиномов для решения повторений (через повторение, которое описывает ).Q|LN|(|LN|)NN

Рафаэль
источник
Не ясно, как ваш ответ отвечает на вопрос. Кроме того, что такое ? LN
Дейв Кларк
1
@Gilles Analytic Combinatorics , книги Эйленберга, книга Берстеля, Рейтенауэр
2012 г.
1
@ Patrick87: 1) Верно, опечатка; Благодарность! 2) Для конечных языков порождающая функция является полиномом (и вместе с тем рациональным). Поскольку , этот подход не будет работать. Связанная теорема начинается с линейного однородного повторения; Я не думаю, что они могут описывать последовательности, которые являются нулевыми для всех (и ненулевыми для хотя бы одного значения). Не уверен, хотя. Если я прав, то утверждение, о котором мы говорим, действительно справедливо только для бесконечных регулярных языков; это не было бы совершенно удивительно, поскольку конечные языки не имеют никакой структуры. Q(Z)знак равно1КN0
Рафаэль
1
@ Рафаэль Да, мое мышление было схожим ... это представляется довольно серьезным недостатком в изложении теоремы, если оно не выполняется для конечных языков, поскольку (а) конечные языки являются регулярными, (б) теорема подразумевает, что конечные языки не являются регулярными, и (c) определение того, является ли язык конечным, (вообще) неразрешимо ... Я имею в виду, что у Myhill-Nerode и леммы прокачки такой проблемы нет; они работают для конечных языков.
Patrick87