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 $ℕ$ é 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} + \dots

com coeficientes $a_{k}$ em $ℕ$ . 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} (\sum_{i = 0}^{k} a_{i} b_{k - i}) 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 $ℚ (x)$ , se existe um conjunto finito de polinômios $p_{0} (x), p_{1} (x), p_{2} (x), \dots, 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} + \dots + 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 Σ^{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 $ℕ$ que é algébrica sobre $ℚ (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 + ϵ)^{n}$ mas $a_{n} \notin O (2 - ϵ)^{n}$ para cada $ϵ > 0$ .

Ver Predefinição:Harv 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}} b a^{n_{2}} b \dots a^{n_{p}} b$ com $p \geq 1$ , $n_{i} > 0$ para $i \in {1, 2, \dots, p}$ , e $n_{j} \neq j$ para algum $j \in {1, 2, \dots, p}$ .

É comparavelmente fácil mostrar que a linguagem $L_{G}$ é livre-do-contexto Predefinição:Harv. 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 - 2 x} - \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 $ℚ (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 Predefinição:Harv para mais detalhes.