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.