Abrir menu principal

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.

Índice

EnunciadoEditar

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

 

com coeficientes   em  . A multiplicação de duas séries de potência   e   é definida de forma esperada como sendo a convolução de duas sequencias   e  :

 


Em particular, nós escrevemos  ,  , e assim por diante. Em analogia aos números algébricos, uma série de potência   é chamada algébrica sobre  , se existe um conjunto finito de polinômios   cada qual com coeficientes de número racional tais como

 

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   é o número de palavras de tamanho   em  , então   é uma série de potência sobre   que é algébrica sobre  .

Provas deste teorema são dadas por Kuich & Salomaa (1985), e por Panholzer (2005).

UsosEditar

Estimativas assintóticasEditar

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   de palavras de comprimento n gerado por G pode ser estimado, à medida que n cresce largamente. Neste caso, obtém-se que   mas   para cada  .

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

Ambiguidade InerenteEditar

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   sobre o alfabeto   consiste das palavras   com  ,   para  , e   para algum  .

É comparavelmente fácil mostrar que a linguagem   é 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  . Isto pode ser provado como segue:

Se   denota o número de palavras de tamanho   em  , então para as séries de potência associadas assegura-se: . Usando métodos de análise complexa, este pode provar que esta função é não-algébrica sobre  . Pelo teorema de Chomsky-Schützenberger, podemos concluir que   não admite uma gramática livre-do-contexto não-ambígua. Ver (Berstel & Boasson 1990) para mais detalhes.

ReferenciasEditar

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