# Teorema da enumeração de Chomsky - Schützenberger

Em teoria da linguagem formal, o teorema da enumeração de Chomsky-Schützenberger é um teorema derivado por Noam Chomsky e Marcel-Paul Schützenberger sobre o número de palavras de um determinado comprimento gerada por uma gramática livre de contexto inequívoca. O teorema fornece uma ligação inesperada entre a teoria das linguagens formais e álgebra abstrata.

## Enunciado

A fim de indicar o teorema, são necessárias algumas noções de álgebra e teoria da linguagem formal.
Uma série de potência sobre $\mathbb {N}$ é uma série infinita de forma
    $f=f(x)=\sum _{k=0}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+\cdots$
com coeficientes $a_{k}$ em $\mathbb {N}$. A multiplicação de duas séries de potência $f$ e $g$ é definida de forma esperada como sendo a convolução de duas sequencias $a_{n}$ e $b_{n}$:
    $f(x)\cdot g(x)=\sum _{k=0}^{\infty }\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)x^{k}.$
Em particular, nós escrevemos $f^{2}=f(x)\cdot f(x)$, $f^{3}=f(x)\cdot f(x)\cdot f(x)$, e assim por diante. Em analogia aos números algébricos, uma série de potência $f(x)$ é chamada algébrica sobre $\mathbb {Q} (x)$, se existe um conjunto finito de polinômios $p_{0}(x),p_{1}(x),p_{2}(x),\ldots ,p_{n}(x)$ cada qual com coeficientes de número racional tais como
    $p_{0}(x)+p_{1}(x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.$
Uma gramática livre-do-contexto é dita ser não-ambígua se toda palavra gerada pela gramática admite uma única árvore sintática, ou, equivalentemente, uma única derivação mais à esquerda.
Tendo estabelecido as noções necessárias, o teorema é enunciado como segue:
Teorema de Chomsky–Schützenberger. Se L é uma linguagem livre de contexto admitindo uma gramática livre de contexto inequívoca, e $a_{k}:=|L\ \cap \Sigma ^{k}|$ é o número de palavras de tamanho $k$ em $L$, então $G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}$ é uma série de potência sobre $\mathbb {N}$ que é algébrica sobre $\mathbb {Q} (x)$.
Provas deste teorema são dadas por Kuich & Salomaa (1985), e por Panholzer (2005).

## Usos
### Estimativas assintóticas

O teorema pode ser usado em combinatórias analíticas para estimar o número de palavras de comprimento n gerados por uma determinada gramática livre de contexto inequívoca, como n cresce expansivamente. O exemplo a seguir é dado por Gruber, Lee & Shallit (2012): a gramática livre de contexto G inequívoca sobre o alfabeto {0,1} tem símbolo inicial S e as seguintes regras:
    S → M | U
    M → 0M1M | ε
    U → 0S | 0M1U
Para se obter uma representação algébrica das séries de potência G(x) associadas com uma dada gramática livre de contexto G, esta representação transforma a gramática em um sistema de equações. Isto é conseguido através da substituição de cada ocorrência de um símbolo de terminal por 'x', cada ocorrência de 'ε' pelo inteiro "1", cada ocorrência de '→' por '=', e cada ocorrência de '|' por '+ ', respectivamente. A operação de concatenação para a caso do lado direito de cada regra corresponde à operação de multiplicação nas equações assim obtidos. Isso produz o seguinte sistema de equações:
    S = M + U
    M = M²x² + 1
    U = Sx + MUx²
Neste sistema de equações, S, M, e L são funções de x, de modo que também se poderia escrever S (x), M (x), e L (x). O sistema de equações pode ser resolvido depois de S, resultando em uma única equação algébrica:
x(2x-1)S^2 + (2x-1)S +1 = 0.
Esta equação quadrática possui duas soluções para S, uma das quais é a série de potência algébrica L (x). Através da aplicação de métodos de análise complexa a esta equação, o número $a_{n}$ de palavras de comprimento n gerado por G pode ser estimado, à medida que n cresce largamente. Neste caso, obtém-se que $a_{n}\in O(2+\epsilon )^{n}$ mas $a_{n}\notin O(2-\epsilon )^{n}$ para cada $\epsilon >0$.
Ver (Gruber, Lee & Shallit 2012) para uma exposição detalhada.

### Ambiguidade Inerente

Em teoria da linguagem formal clássica, o teorema pode ser usado para provar que certas linguagens livres de contexto são inerentemente ambíguas. Por exemplo, a linguagem Goldstine $L_{G}$ sobre o alfabeto $\{a,b\}$ consiste das palavras $a^{n_{1}}ba^{n_{2}}b\cdots a^{n_{p}}b$ com $p\geq 1$, $n_{i}>0$ para $i\in \{1,2,\ldots ,p\}$, e $n_{j}\neq j$ para algum $j\in \{1,2,\ldots ,p\}$.
É comparavelmente fácil mostrar que a linguagem $L_{G}$ é livre-do-contexto (Berstel & Boasson 1990). A parte mais difícil é mostrar que não há nenhuma gramática não-ambígua que gera $L_{G}$. Isto pode ser provado como segue:
Se $g_{k}$ denota o número de palavras de tamanho $k$ em $L_{G}$, então para as séries de potência associadas assegura-se:$G(x)=\sum _{k=0}^{\infty }g_{k}x^{k}={\frac {1-x}{1-2x}}-{\frac {1}{x}}\sum _{k\geq 1}x^{k(k+1)/2-1}$. Usando métodos de análise complexa, este pode provar que esta função é não-algébrica sobre $\mathbb {Q} (x)$. Pelo teorema de Chomsky-Schützenberger, podemos concluir que $L_{G}$ não admite uma gramática livre-do-contexto não-ambígua. Ver (Berstel & Boasson 1990) para mais detalhes.

## Referencias

    Berstel, Jean; Boasson, Luc (1990). «Context-free languages» (PDF). In: van Leeuwen, Jan. Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. [S.l.]: Elsevier and MIT press. pp. 59–102. ISBN 0-444-88074-7
    Chomsky, Noam; Schützenberger, Marcel-Paul (1963). «The Algebraic Theory of Context-Free Languages» (PDF). In P. Braffort and D. Hirschberg, eds., Computer Programming and Formal Systems (pp. 118–161). Amsterdam: North-Holland
    Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge: Cambridge University Press. ISBN 978-0-521-89806-5
    Gruber, Hermann; Lee, Jonathan; Shallit, Jeffrey (2012). «Enumerating regular expressions and their languages». arXiv:1204.4982 [cs.FL]
    Kuich, Werner; Salomaa, Arto (1985). Semirings, Automata, Languages. Berlin: Springer-Verlag. ISBN 978-3-642-69961-0
    Panholzer, Alois (2005). «Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function». Journal of Automata, Languages and Combinatorics. 10: 79–97