Twierdzenie Chomsky'ego – Schützenbergera o wyliczeniu

W teorii języka formalnego twierdzenie wyliczeniowe Chomsky'ego – Schützenbergera jest twierdzeniem wyprowadzonym przez Noama Chomsky'ego i Marcela-Paula Schützenbergera na temat liczby słów o danej długości generowanych przez jednoznaczną gramatykę bezkontekstową . Twierdzenie to zapewnia nieoczekiwany związek między teorią języków formalnych a algebrą abstrakcyjną .

Oświadczenie

Do sformułowania twierdzenia potrzeba kilku pojęć z algebry i teorii języka formalnego.

Niech $całkowitych .$ zbiór nieujemnych liczb Szereg potęgowy nad $_$ nieskończonym szeregiem formy

${\ Displaystyle f = f (x) = \ suma _ {k$

ze współczynnikami ${\ displaystyle a_ {k}}$ w ${\ displaystyle \ mathbb {N}}$ . Mnożenie dwóch formalnych szeregów potęgowych i ${\ displaystyle$$} jest$${\ displaystyle b_ {} n}}$ w oczekiwany sposób jako splot sekwencji ${\ displaystyle a_ {n}}$ i n :

${\ Displaystyle f (x) \ cdot g (x) = \ suma _ {k = 0} ^ {\ infty} \ lewo (\ suma _ {i = 0} ^ {k} a_ {i} b_ {ki} \right)x^{k}.}$

W szczególności piszemy ${\ Displaystyle f ^ {2} = f (x) \ cdot f (x)}$ , ${\ Displaystyle f ^ {3} = f (x) \ cdot f (x) \ cdot f (x)} i$ tak dalej. Analogicznie do $liczb$ algebraicznych , potęgowy $nazywa$ algebraicznym nad istnieje ${\ Displaystyle p_ {0} (x), p_ {1} (x), p_ {2} (x) ,\ldots ,p_{n}(x)}$ każdy z wymiernymi współczynnikami takimi, że

${\ Displaystyle p_ {0} (x) + p_ {1} (x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.}$

Mówi się, że gramatyka bezkontekstowa jest jednoznaczna , jeśli każdy ciąg generowany przez gramatykę dopuszcza unikalne drzewo analizy lub, równoważnie, tylko jedno skrajne lewe wyprowadzenie . Po ustaleniu niezbędnych pojęć twierdzenie brzmi następująco.

Twierdzenie Chomsky'ego-Schützenbergera . Jeśli $jest$ językiem ${\ Displaystyle a_ {k}: =| L \ \ cap \ Sigma ^ {k}|}$ jednoznaczną gramatykę bezkontekstową, a = to liczba słów o długości ${\ displaystyle k}$ w ${\ displaystyle L}$ , a następnie ${\ Displaystyle G (x) = \ suma _ {k = 0} ^ {\ infty} a_ {k} x ^ {k}} to szereg potęgowy$ nad ${\ Displaystyle \ mathbb { N} }$ to jest algebraiczne względem ${\ Displaystyle \ mathbb {Q} (x)}$ .

Dowody tego twierdzenia podają Kuich i Salomaa (1985) oraz Panholzer (2005) .

Stosowanie

Szacunki asymptotyczne

Twierdzenie to może być użyte w kombinatoryce analitycznej do oszacowania liczby słów o długości n generowanych przez daną jednoznaczną gramatykę bezkontekstową, gdy n rośnie. Poniższy przykład podają Gruber, Lee & Shallit (2012) : jednoznaczna gramatyka bezkontekstowa G nad alfabetem {0,1} ma symbol startu S i następujące reguły

S → M. | U

M → 0 M 1 M | ε

U → 0 S | 0 M 1 U .

uzyskać algebraiczną reprezentację szeregu potęgowego związanego z daną gramatyką bezkontekstową $G$ układ równań Osiąga się to poprzez zastąpienie każdego wystąpienia symbolu końcowego przez x , każdego wystąpienia ε liczbą całkowitą „1”, każdego wystąpienia „→” przez „=” i każdego wystąpienia „|” odpowiednio przez „+”. Operacja konkatenacji po prawej stronie każdej reguły odpowiada operacji mnożenia w otrzymanych w ten sposób równaniach. Daje to następujący układ równań:

S = M + U

M = M ² x ² + 1

U = Sx + MUx ²

W tym układzie równań S , M i U są funkcjami x , więc można również napisać ${\ Displaystyle S (x)}$ , ${\ Displaystyle M (x)}$ i ${\ Displaystyle U (x)}$ . Układ równań można rozwiązać po S , co daje pojedyncze równanie algebraiczne:

${\ Displaystyle x (2x-1) S ^ {2} + (2x-1) S + 1 = 0}$ .

To równanie kwadratowe ma dwa rozwiązania dla S , z których jednym jest algebraiczny szereg potęgowy ${\ Displaystyle G (x)}$ . Stosując metody analizy złożonej do tego równania, można oszacować liczbę $.$ o długości n generowanych przez G , gdy n W tym przypadku otrzymuje się ${\ Displaystyle a_ {n} \ in O (2+ \ epsilon) ^ {n}}$ ale ${\ displaystyle a_ {n} \ notin O (2- \ epsilon) ^ {n}}$ dla każdego ${\ displaystyle \ epsilon > 0}$ . Zobacz ( Gruber, Lee & Shallit 2012 ), aby zapoznać się ze szczegółową ekspozycją.

Poniższy przykład pochodzi z:

$${\ Displaystyle \ lewo \ {{\ rozpocząć {tablica}} {l} {S \ rightarrow XY}\\{T\rightarrow aT|TbT|YcY}\\{Y\rightarrow YaY|cY|abTaYYa|X}\\{X\rightarrow a|b|c}\end{tablica}}\Rightarrow \ lewo\{{\początek{tablica}{l}s(z)=x(z)y(z)\\t(z)=zt(z)+zt(z)^{2}+zy(z) ^{2}\\y(z)=zy(z)^{2}+zy(z)+z^{4}t(z)y(z)^{2}+x(z)\\x (z)=3z\koniec{tablica}}\prawo.\prawo.}$$

co upraszcza

$${\ Displaystyle s (z) ^ {8} -27 \ lewo (z ^ {3} -z ^ {2}\right)s(z)^{5}+\ldokropki +59049z^{10}=0}$$

Nieodłączna niejednoznaczność

W klasycznej formalnej teorii języków twierdzenie to może być użyte do udowodnienia, że ​​pewne języki bezkontekstowe są z natury niejednoznaczne . Na przykład język Goldstine nad alfabetem $Displaystyle \$$}$${\ Displaystyle a ^ {n_ {1}} ba ^ {n_ {2}} b \ cdots a ^ {n_ {p}} b} z$ składa się ze słów p $\ Displaystyle p \ geq 1}$ , ${\ Displaystyle n_ {i}> 0}$ dla ${\ Displaystyle i \ w \ {1,2, \ ldots, p \}}$ i ${\ Displaystyle n_ {j} \ neq j}$ dla niektórych ${\ Displaystyle j \ in \ {1,2, \ ldots, p \}}$ .

Stosunkowo łatwo jest pokazać, że język $jest$ ( Berstel & Boasson 1990 ) Trudniejszą częścią jest pokazanie, że nie istnieje jednoznaczna gramatyka, która generuje ${\ displaystyle L_ {G}}$ . Można to udowodnić w następujący sposób: Jeśli $k$ liczbę słów o długości $Displaystyle$ L $L_ {G}}$ , to dla powiązanego szeregu potęg zachodzi k {\ displaystyle ${\ Displaystyle G (x) = \ suma _ {k=0}^{\infty}g_{k}x^{k}={\frac {1-x}{1-2x}}-{\frac {1}{x}}\suma _{k \geq 1}x^{k(k+1)/2-1}}$ . Używając metod z analizy złożonej , można udowodnić, że ta funkcja nie jest algebraiczna względem ${\ Displaystyle \ mathbb {Q} (x)}$ . Z twierdzenia Chomsky'ego-Schützenbergera można wywnioskować, że $dopuszcza$ jednoznacznej gramatyki bezkontekstowej. Zobacz ( Berstel & Boasson 1990 ) dla szczegółowego opisu.

•   Berstel, Jean; Boasson, Luc (1990). „Języki bezkontekstowe” (PDF) . W van Leeuwen, Jan (red.). Podręcznik informatyki teoretycznej, tom B: Modele formalne i semantyka . Elsevier i MIT Press. s. 59–102. ISBN 0-444-88074-7 .
• Chomsky, Noam ; Schützenberger, Marcel-Paul (1963). „Algebraiczna teoria języków bezkontekstowych” (PDF) . W P. Braffort i D. Hirschberg, red., Programowanie komputerowe i systemy formalne (s. 118–161) . Amsterdam: Holandia Północna.
•   Flajolet Filip ; Sedgewick, Robert (2009). Kombinatoryka analityczna . Cambridge: Cambridge University Press . ISBN 978-0-521-89806-5 .
• Gruber, Hermann; Lee, Jonathan; Szallit, Jeffrey (2012). „Wyliczanie wyrażeń regularnych i ich języków”. arXiv : 1204,4982 [ cs.FL ].
•   Kuich, Werner; Salomaa, Arto (1985). Semiringi, automaty, języki . Berlin: Springer-Verlag . ISBN 978-3-642-69961-0 .
• Panholzer, Alois (2005). „Podstawy Gröbnera i definiujący wielomian bezkontekstowej funkcji generującej gramatykę”. Journal of Automata, języki i kombinatoryka . 10 : 79–97.