Chomsky–Schützenbergers uppräkningssats

I formell språkteori är Chomsky –Schützenbergers uppräkningssats en sats som härleds av Noam Chomsky och Marcel-Paul Schützenberger om antalet ord av en given längd som genereras av en entydig kontextfri grammatik . Teoremet ger en oväntad koppling mellan teorin om formella språk och abstrakt algebra .

Påstående

För att kunna ange satsen behövs några föreställningar från algebra och formell språkteori.

Låt $\mathbb {N}$ beteckna mängden icke-negativa heltal. En potensserie över $\mathbb {N}$ är en oändlig serie av formen

$f=f(x)=\summa _{k= 0}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3 }+\cdots$

med koefficienter $a_{k}$ i $\mathbb {N}$ . Multiplikationen av två formella potensserier $f$ och $g$ definieras på det förväntade sättet som faltningen av sekvenserna a $\displaystyle a_{n}}$ och $b_{ n}$ :

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

I synnerhet skriver vi $f^{2}=f(x)\cdot f(x)$ , $f^{3}=f(x)\cdot f(x)\cdot f(x)$ och så vidare. I analogi med algebraiska tal kallas en potensserie $f(x)$ algebraisk över $\mathbb {Q} (x)$ , om det finns en ändlig uppsättning polynom $p_{0}(x),p_{1}(x),p_{2}(x) ,\ldots ,p_{n}(x)$ var och en med rationella koefficienter så att

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

En kontextfri grammatik sägs vara otvetydig om varje sträng som genereras av grammatiken tillåter ett unikt analysträd eller, motsvarande, bara en härledning längst till vänster . Efter att ha fastställt de nödvändiga begreppen, anges satsen enligt följande.

Chomsky–Schützenbergers sats . Om $L$ är ett sammanhangsfritt språk som tillåter en entydig sammanhangsfri grammatik, och $a_{k}:=|L\ \cap \Sigma ^{k}|$ är antalet ord med längden $k$ i $L$ , sedan ${\displaystyle G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}} är$ en potensserie över $\mathbb { N}$ som är algebraisk över $\mathbb {Q} (x)$ .

Bevis för detta teorem ges av Kuich & Salomaa (1985) och av Panholzer (2005) .

Användande

Asymptotiska uppskattningar

Satsen kan användas i analytisk kombinatorik för att uppskatta antalet ord med längden n som genereras av en given entydig kontextfri grammatik, när n växer sig stort. Följande exempel ges av Gruber, Lee & Shallit (2012) : den entydiga kontextfria grammatiken G över alfabetet {0,1} har startsymbolen S och följande regler

S → M | U

M → 0 M 1 M | ε

U → 0 S | 0 M 1 U .

För att få en algebraisk representation av potensserien $G(x)$ associerad med en given kontextfri grammatik G , transformerar man grammatiken till ett ekvationssystem. Detta uppnås genom att ersätta varje förekomst av en terminalsymbol med x , varje förekomst av ε med heltal '1', varje förekomst av '→' med '=' och varje förekomst av '|' med '+', respektive. Sammankopplingsoperationen till höger om varje regel motsvarar multiplikationsoperationen i de sålunda erhållna ekvationerna. Detta ger följande ekvationssystem:

S = M + U

M = M ² x ² + 1

U = Sx + MUx ²

I detta ekvationssystem är S , M och U funktioner av x , så man kan också skriva ${\displaystyle S(x)} ,$ M $\displaystyle M(x)}$ och $U(x)$ . Ekvationssystemet kan lösas efter S , vilket resulterar i en enda algebraisk ekvation:

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

Denna andragradsekvation har två lösningar för S , varav en är den algebraiska potensserien $G(x)$ . Genom att tillämpa metoder från komplex analys på denna ekvation kan antalet $a_{n}$ av ord med längden n som genereras av G uppskattas, när n växer sig stort. I detta fall får man $a_{n}\in O(2+\epsilon )^{n}$ men ${\ displaystyle a_{n}\notin O(2-\epsilon )^{n}}$ för varje $\epsilon >0$ . Se ( Gruber, Lee & Shallit 2012) för en detaljerad utläggning.

Följande exempel är från:

$$\left\{{\begin{array}{l }{S\ högerpil XY}\\{T\högerpil aT|TbT|YcY}\\{Y\högerpil YaY|cY|abTaYYa|X}\\{X\högerpil a|b|c}\end{array}}\Högerpil \ vänster\{{\begin{array}{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\end{array}}\right.\right.$$

vilket förenklar till

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

Inneboende tvetydighet

I klassisk formell språkteori kan teoremet användas för att bevisa att vissa kontextfria språk är i sig tvetydiga . Till exempel består Goldstine-språket $L_{G}$ över alfabetet $\{a,b\}$ av orden $a^{n_{1}}ba^{n_{2}}b\cdots a^{n_{p}}b$ med $p\geq 1$ , $n_{i}>0$ för $i\in \{1,2,\ldots ,p\}$ och $n_{j}\neq j$ för vissa $j\in \{1,2,\ldots ,p\}$ .

Det är jämförelsevis lätt att visa att språket $L_{G}$ är kontextfritt ( Berstel & Boasson 1990) . Den svårare delen är att visa att det inte finns en entydig grammatik som genererar $L_{G}$ . Detta kan bevisas enligt följande: Om $g_{k}$ anger antalet ord med längden $k$ i $L_{G}$ , gäller för den tillhörande potensserien $G(x)=\summa _ {k=0}^{\infty }g_{k}x^{k}={\frac {1-x}{1-2x}}-{\frac {1}{x}}\summa _{k \geq 1}x^{k(k+1)/2-1}$ . Med hjälp av metoder från komplex analys kan man bevisa att denna funktion inte är algebraisk över $\mathbb {Q} (x)$ . Genom Chomsky-Schützenbergers sats kan man dra slutsatsen att $L_{G}$ inte medger en entydig kontextfri grammatik. Se ( Berstel & Boasson 1990 ) för detaljerad redogörelse.

•   Berstel, Jean; Boasson, Luc (1990). "Kontextfria språk" (PDF) . I van Leeuwen, Jan (red.). Handbook of Theoretical Computer Science, Volym B: Formella modeller och semantik . Elsevier och MIT pressar. s. 59–102. ISBN 0-444-88074-7 .
• Chomsky, Noam ; Schützenberger, Marcel-Paul (1963). "Den algebraiska teorin om sammanhangsfria språk" (PDF) . I P. Braffort och D. Hirschberg, red., Computer Programming and Formal Systems (s. 118–161) . Amsterdam: Nord-Holland.
•   Flajolet, Philippe ; Sedgewick, Robert (2009). Analytisk kombinatorik . Cambridge: Cambridge University Press . ISBN 978-0-521-89806-5 .
• Gruber, Hermann; Lee, Jonathan; Shallit, Jeffrey (2012). "Räkna upp reguljära uttryck och deras språk". arXiv : 1204.4982 [ cs.FL ].
•   Kuich, Werner; Salomaa, Arto (1985). Semirings, automater, språk . Berlin: Springer-Verlag . ISBN 978-3-642-69961-0 .
• Panholzer, Alois (2005). "Gröbner-baser och det definierande polynomet för en kontextfri grammatikgenererande funktion". Journal of Automata, Languages ​​and Combinatorics . 10 : 79–97.