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.

Afirmacao

A fim de indicar o teorema, são necessárias algumas noções de álgebra e teoria da linguagem formal.

Uma série podersa 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 poderosas $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 poderosa $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 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

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 grande. 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 → S | 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 $a_{n}\in O(2+\epsilon )^{n}$ but $a_{n}\notin O(2-\epsilon )^{n}$ para cada $\epsilon >0$.

Ver (Gruber, Lee & Shallit 2012) para uma exposição detalhada.