Liczba słów o określonej długości w zwykłym języku

Czy istnieje algebraiczna charakterystyka liczby słów o danej długości w zwykłym języku?

Wikipedia podaje wynik nieco nieprecyzyjnie:

Dla każdego języka regularnego istnieje stałych i wielomiany tak, że dla każdego numer z słowa o długości w spełnia równanie . $L$ $\lambda_1,\,\ldots,\,\lambda_k$ $p_1(x),\,\ldots,\,p_k(x)$ $n$ $s_L(n)$ $n$ $L$ $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$

Nie jest określone, w jakiej przestrzeni żyje ( , jak przypuszczam) i czy funkcja musi mieć nieujemne wartości całkowite w całym . Chciałbym uzyskać dokładne oświadczenie oraz szkic lub odniesienie do dowodu. $\lambda$ $\mathbb{C}$ $\mathbb{N}$

Pytanie dodatkowe: czy jest odwrotnie, tzn. Biorąc pod uwagę funkcję tej formy, czy zawsze istnieje język regularny, którego liczba słów na długość jest równa tej funkcji?

_{To pytanie uogólnia Liczba słów w zwykłym języku $(00)^*$}

formal-languages regular-languages word-combinatorics Gilles „SO- przestań być zły”
źródło

szkic dowodu jest tutaj

Artem Kaznatcheev

@ArtemKaznatcheev Ciekawe dzięki. Czy zastanowiłbyś się nad przeniesieniem odpowiedzi na to pytanie, które lepiej pasuje?

Gilles 'SO - przestań być zły'

Wydaje mi się, że to pytanie jest nieco zbędne (choć bardziej ogólne). Uogólniając moje podejście do dowodu, jest trochę owłosione, ale przyjdę po kolacji.

Artem Kaznatcheev

@ArtemKaznatcheev Thanks. Miałem problem z drugą częścią twojej odpowiedzi, obejmującą redukowalne DFA.

Gilles 'SO - przestań być zły'

@vzn Klasycznym faktem jest to, że funkcja generowania liczby słów w zwykłym języku jest racjonalna, co natychmiast implikuje formułę OP (w poprawnej formie). Trudną częścią jest wydobycie asymptotyków. Aby uzyskać szczegółowe informacje, możesz sprawdzić (na przykład) książkę Analytic Combinatorics wspomnianą w mojej odpowiedzi.

Yuval Filmus

Odpowiedzi:

Biorąc pod uwagę zwykły język , rozważ niektóre DFA akceptujące , niech będzie jego macierzą transferu ( to liczba krawędzi prowadzących od stanu do stanu ), niech będzie wektorem charakterystycznym stanu początkowego i niech będzie charakterystycznym wektorem stanów akceptujących. Następnie $L$ $L$ $A$ $A_{ij}$ $i$ $j$ $x$ $y$

s_{L.} (n) = x^{T.} {ZA}^{n} y .

$s_L(n) = x^T A^n y.$

Twierdzenie Jordana stwierdza, że nad liczbami zespolonymi jest podobny do macierzy z blokami jednej z form Jeśli , to moce tych bloków są $A$

(\begin{matrix} λ \end{matrix}), (\begin{matrix} λ & 1 \\ 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 \\ 0 & λ & 1 \\ 0 & 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 & 0 \\ 0 & λ & 1 & 0 \\ 0 & 0 & λ & 1 \\ 0 & 0 & 0 & λ \end{matrix}), \dots

$\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$

λ \neq 0

$\lambda \neq 0$

n

$n$

(\begin{matrix} λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} \\ 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2)}) λ^{n - 2)} \\ 0 & λ^{n} & n λ^{n - 1} \\ 0 & 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2)}) λ^{n - 2)} & (\binom{n}{3)}) λ^{n - 3)} \\ 0 & λ^{n} & n λ^{n - 1} & (\binom{n}{2)}) λ^{n - 2)} \\ 0 & 0 & λ^{n} & n λ^{n - 1} \\ 0 & 0 & 0 & λ^{n} \end{matrix}), \dots

$\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$ Oto jak otrzymaliśmy tych wzorach zapisać jako blok . Kolejne moce są kolejnymi wtórnymi przekątnymi macierzy.

B = λ + N

$B = \lambda + N$

N

$N$

λ

$\lambda$

N

$N$

b^{n} = (λ + n)^{N.} = λ^{n} + n λ^{n - 1} N. + (\binom{n}{2)}) λ^{n - 2)} {N.}^{2)} + \dots .

$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$ Gdy , blok jest zerowy i otrzymujemy następujące macierze (notacja wynosi jeśli a w przeciwnym razie ):

λ = 0

$\lambda = 0$

[n = k]

$[n = k]$

1

$1$

n = k

$n=k$

0

$0$

(\begin{matrix} [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] \\ 0 & [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] & [n = 2)] \\ 0 & [n = 0] & [n = 1] \\ 0 & 0 & [n = 0] \end{matrix}), (\begin{matrix} [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{matrix})

$\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}$

Podsumowując, każdy wpis w ma postać lub o postaci , a my wywnioskujemy, że dla niektórych złożonych i złożonych wielomianów . W szczególności, dla wystarczająco dużych , To jest dokładne określenie wyniku. $A^n$ $\binom{n}{k} \lambda^{n-k}$ $[n=k]$

s_{L.} (n) = \sum_{ja} p_{ja} (n) λ_{ja}^{n} + \sum_{jot} {do}_{jot} [n = jot],

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

λ_{i}, c_{j}

$\lambda_i,c_j$

p_{i}

$p_i$ $n$

s_{L.} (n) = \sum_{ja} p_{ja} (n) λ_{ja}^{n} .

$s_L(n) = \sum_i p_i(n) \lambda_i^n.$

Możemy kontynuować i uzyskać asymptotyczne informacje o , ale jest to zaskakująco nietrywialne. Jeśli istnieje unikalny największej wielkości, powiedzmy , to Sprawy komplikują się, gdy jest kilka o największej wielkości. Zdarza się, że ich kąt musi być racjonalny (tzn. Do rangi, są korzeniami jedności). Jeśli LCM mianowników wynosi , to asymptotyki będą bardzo zgodne z resztą modulo . W przypadku niektórych z tych reszt wszystkie $s_L(n)$ $\lambda_i$ $\lambda_1$

s_{L.} (n) = p_{1} (n) λ_{1}^{n} (1 + o (1)) .

$s_L(n) = p_1(n) \lambda_1^n (1 + o(1)).$

λ

$\lambda$

d

$d$

s_{L}

$s_L$

n

$n$

d

$d$

λ

$\lambda$ s największej wielkości anulują, a następnie asymptotyki „spadają” i musimy powtórzyć tę procedurę. Zainteresowany czytelnik może sprawdzić szczegóły w Kombinatoryce analitycznej Flajoleta i Sedgewicka , Twierdzenie V.3. Udowadniają, że dla niektórych , liczb całkowitych i reals ,

d

$d$

p_{0}, \dots, p_{d - 1}

$p_0,\ldots,p_{d-1}$

λ_{0}, \dots, λ_{d - 1}

$\lambda_0,\ldots,\lambda_{d-1}$

s_{L.} (n) = n^{p_{n (\mod re)}} λ_{n (\mod re)}^{n} (1 + o (1)) .

$s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)).$

Yuval Filmus
źródło

Niech zwykłym językiem i $L \subseteq \Sigma^*$

$\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$

jego funkcja generująca , gdzie a więc . $L_n = L \cap \Sigma^n$ $|L_n|=s_L(n)$

Wiadomo, że jest racjonalny , tj $L(z)$

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

z wielomianami ; jest to najłatwiejsze do przełożenia na przekształcenie gramatyki prostoliniowej dla na układ równań (liniowy!), którego rozwiązaniem jest . $P,Q$ $L$ $L(z)$

Korzenie są zasadniczo odpowiedzialne za, co prowadzi do formularza podanego na Wikipedii. Jest to bezpośrednio związane z metodą charakterystycznych wielomianów do rozwiązywania nawrotów (poprzez wzorzec, który opisuje ). $Q$ $|L_n|$ $(|L_n|)_{n \in \mathbb{N}}$

Raphael
źródło

Nie jest jasne, w jaki sposób twoja odpowiedź odpowiada na pytanie. Co to jest ?

L_{n}

$L_n$

Dave Clarke

@Gilles Analytic Combinatorics , książki Eilenberga, książki Berstela, Reutenauera

uli

@Gilles Automata-Theoretic Aspects of Formal Power Series.

@ Patrick87: 1) Racja, literówka; dzięki! 2) W przypadku języków skończonych funkcja generująca jest wielomianem (i tym samym racjonalnym). Ponieważ , to podejście nie będzie działać. Połączone twierdzenie zaczyna się od liniowego jednorodnego nawrotu; Nie sądzę, że mogą opisywać sekwencje, które są zerowe dla wszystkich (i niezerowe dla co najmniej jednej wartości). Jednak nie jestem pewien. Jeśli mam rację, stwierdzenie, o którym mówimy, rzeczywiście dotyczy tylko nieskończonych języków regularnych; nie byłoby to całkowicie zaskakujące, ponieważ języki skończone nie mają żadnej struktury.

Q (z) = 1

$Q(z)=1$

k \geq n_{0}

$k \geq n_0$

Raphael

@Raphael Tak, moje myślenie było podobne ... wydaje się, że jest to dość poważna wada w prezentacji twierdzenia, jeśli nie dotyczy to języków skończonych, ponieważ (a) języki skończone są regularne, (b) twierdzenie sugeruje, że skończone języki nie są regularne, i (c) ustalenie, czy język jest skończony, jest (ogólnie) nierozstrzygalne ... Mam na myśli, że Myhill-Nerode i lemat pompujący nie mają tego problemu; działają dla języków skończonych.

Patrick87