Lema de Ogden

Na ciência da computação teórica , o lema de Ogden é um resultado da teoria da linguagem análoga ao lema estelar . É usado principalmente para demonstrar que algumas línguas não são algébricas . Seu nome é uma homenagem a William F. Ogden, um teórico americano da computação que o publicou em 1968.

O lema de Ogden é uma versão mais elaborada do lema de iteração para linguagens algébricas , também conhecido como lema de Bar-Hillel, Perles e Shamir .

Existem linguagens que satisfazem o lema de Ogden, mas que não são algébricas. Este lema fornece uma condição necessária para linguagens algébricas, mas não uma condição suficiente. É muito útil, em sua versão gramatical, provar que certas línguas são inerentemente ambíguas .

Afirmações

Lema de Ogden

Dada uma palavra , onde são letras, chamamos de posição em todo o conjunto . Uma escolha de posições distintas ou marcadas em (esta é a terminologia tradicional) é simplesmente um subconjunto de posições contendo elementos. Com essas definições, o lema é o seguinte: C=no1no2⋯nonão{\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}noeu{\ displaystyle a_ {i}}C{\ displaystyle w}{1,2,...,não}{\ displaystyle \ {1,2, \ ldots, n \}}NÃO{\ displaystyle N} C{\ displaystyle w}eu⊂{1,2,...,não}{\ displaystyle I \ subset \ {1,2, \ ldots, n \}}NÃO{\ displaystyle N}

Lema de Ogden  -  Let ser uma linguagem algébrica . Existe um número inteiro tal que para qualquer palavra de comprimento , e para qualquer escolha de posições distintas em , existe uma fatoração como: eu{\ displaystyle L}NÃO{\ displaystyle N}C{\ displaystyle w}eu{\ displaystyle L}|C|≥NÃO{\ displaystyle | w | \ geq N}NÃO{\ displaystyle N}C{\ displaystyle w}C=xvocêyvz{\ displaystyle w = xuyvz}

1. ( e e ) ou ( e e ) contêm pelo menos uma posição distinta;x{\ displaystyle x}você{\ displaystyle u}y{\ displaystyle y}y{\ displaystyle y}v{\ displaystyle v}z{\ displaystyle z}
2. vocêyv{\ displaystyle uyv}contém no máximo posições distintas;NÃO{\ displaystyle N}
3. xvocênãoyvnãoz∈eu{\ displaystyle xu ^ {n} yv ^ {n} z \ in L}para tudo .não≥0{\ displaystyle n \ geq 0}

O menor inteiro para o qual a afirmação é verdadeira é chamado de constante de Ogden . NÃO{\ displaystyle N}

Variante gramatical

Existe uma variante gramatical do lema de Ogden: ele diz que o par iterativo pode ser escolhido gramaticalmente . Esta variante é muito útil em certos casos e, em particular, para linguagens inerentemente ambíguas. Aqui está a declaração: (x,você,y,v,z){\ displaystyle (x, u, y, v, z)}

Lema de Ogden (variante gramatical)  -  Seja uma gramática de axioma algébrico . Existe um número inteiro tal que para qualquer palavra que derive de comprimento , e para qualquer escolha de posições distintas em , existe uma fatoração como: G{\ displaystyle G}S{\ displaystyle S}NÃO{\ displaystyle N}C{\ displaystyle w}S{\ displaystyle S}|C|≥NÃO{\ displaystyle | w | \ geq N}NÃO{\ displaystyle N}C{\ displaystyle w}C=xvocêyvz{\ displaystyle w = xuyvz}

1. ( e e ) ou ( e e ) contêm pelo menos uma posição distinta;x{\ displaystyle x}você{\ displaystyle u}y{\ displaystyle y}y{\ displaystyle y}v{\ displaystyle v}z{\ displaystyle z}
2. vocêyv{\ displaystyle uyv}contém no máximo posições distintas;NÃO{\ displaystyle N}
3. Existe uma variável como .X{\ displaystyle X}S→∗xXz, X→∗vocêXv, X→∗y{\ displaystyle S {\ stackrel {*} {\ to}} xXz, \ X {\ stackrel {*} {\ to}} uXv, \ X {\ stackrel {*} {\ to}} y}

Nesse enunciado, a palavra pode conter variáveis ​​da gramática: ela pertence à “linguagem estendida” constituída pela definição de todas as palavras derivadas , quer contenham variáveis ​​ou não. C{\ displaystyle w}S{\ displaystyle S}

Exemplos de aplicação

Linguagens não algébricas

• A linguagem não é algébrica. Para vê-lo, distinguimos na palavra as letras iguais a . Ao aplicar o lema, variamos o número de letras . Devemos ainda distinguir o caso em que o fator é vazio ou não, mas à medida que iteramos este fator, ele só pode ser formado por letras do mesmo tipo, e não podemos compensar o aumento de letras e , ao mesmo tempo, d ' onde a contradição.eu={nonãobnãovsnão∣não⩾0}{\ displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ geqslant 0 \}}noNÃObNÃOvsNÃO{\ displaystyle a ^ {N} b ^ {N} c ^ {N}}no{\ displaystyle a}no{\ displaystyle a}v{\ displaystyle v}b{\ displaystyle b}vs{\ displaystyle c}

• A linguagem não é algébrica. Desta vez, aplicamos a variante gramatical do lema à palavra , onde é a constante de Ogden, e onde as letras distintas são as letras . Existem derivaçõeseu={nombnãovsmdnão∣não,m≥0}{\ displaystyle L = \ {a ^ {m} b ^ {n} c ^ {m} d ^ {n} \ mid n, m \ geq 0 \}}C=noNÃObNÃOvsNÃOdNÃO{\ displaystyle w = a ^ {N} b ^ {N} c ^ {N} d ^ {N}}NÃO{\ displaystyle N}b{\ displaystyle b}

S→∗noNÃObkXdℓ, X→∗beuXdeu, X→∗bk¯vsNÃOdℓ¯{\ displaystyle S {\ stackrel {*} {\ to}} a ^ {N} b ^ {k} Xd ^ {\ ell}, \ X {\ stackrel {*} {\ to}} b ^ {i} Xd ^ {i}, \ X {\ stackrel {*} {\ to}} b ^ {\ bar {k}} c ^ {N} d ^ {\ bar {\ ell}}} com . Aplicamos o lema uma segunda vez, à palavra , onde desta vez são as letras que se distinguem. Obtemos um par iterativo contendo letras iteradas, mas sem letras , contradições.NÃO=k+eu+k¯=ℓ+eu+ℓ¯{\ displaystyle N = k + i + {\ bar {k}} = \ ell + i + {\ bar {\ ell}}}noNÃObkXdℓ{\ displaystyle a ^ {N} b ^ {k} Xd ^ {\ ell}}no{\ displaystyle a}no{\ displaystyle a}d{\ displaystyle d}

Linguagens não algébricas que satisfazem o lema

O lema de Odgen é uma condição necessária, mas não suficiente para linguagens algébricas.

• A linguagem não é algébrica, porque sendo uma linguagem limitada por um alfabeto de duas letras, seu complemento (em relação a ) é que não é algébrico. No entanto, a linguagem confirma o lema de Ogden.eu={nonãobm∣não≠m}∪{nonãobnão∣não não primeiro }{\ displaystyle L = \ {a ^ {n} b ^ {m} \ mid n \ neq m \} \ cup \ {a ^ {n} b ^ {n} \ mid n {\ text {not prime}} \}}no∗b∗{\ displaystyle a ^ {*} b ^ {*}}{nonãobnão∣não primeiro }{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n {\ text {primeiro}} \}}
• A linguagem não é algébrica, mas o lema de Ogden não pode prová-lo porque não há como evitar a iteração da letra inicial.eu=b∗∪nonono∗b∗∪{nobp∣p primeiro }{\ displaystyle L = b ^ {*} \ cup aaa ^ {*} b ^ {*} \ cup \ {ab ^ {p} \ mid p {\ text {first}} \}}no{\ displaystyle a}

Linguagem inerentemente ambígua

• A linguagem é inerentemente ambígua. Uma linguagem é inerentemente ambígua se todas as gramáticas que a geram são ambíguas. Primeiro aplicamos a variante do lema à palavraeu={nonãobnãovsm∣não,m≥0}∪{nombnãovsnão∣não,m≥0}{\ displaystyle L = \ {a ^ {n} b ^ {n} c ^ {m} \ mid n, m \ geq 0 \} \ xícara \ {a ^ {m} b ^ {n} c ^ {n } \ mid n, m \ geq 0 \}}C=noNÃObNÃOvsNÃO+NÃO!{\ displaystyle w = a ^ {N} b ^ {N} c ^ {N + N!}}onde está a constante de Ogden, e distinguindo entre letras . Existe uma derivaçãoNÃO{\ displaystyle N}b{\ displaystyle b}S→∗xXz→∗xvocêXvz→∗xvocêyvz{\ displaystyle S {\ stackrel {*} {\ to}} xXz {\ stackrel {*} {\ to}} xuXvz {\ stackrel {*} {\ to}} xuyvz},e as condições implicam que e para um inteiro . Ao iterar vezes a derivaçãovocê=noeu{\ displaystyle u = a ^ {i}}v=beu{\ displaystyle v = b ^ {i}}0≤eu≤NÃO{\ displaystyle 0 \ leq i \ leq N}NÃO!/eu{\ displaystyle N! / i}X→∗vocêXv{\ displaystyle X {\ stackrel {*} {\ to}} uXv}obtemos uma árvore de derivação para a palavra . Esta árvore contém uma subárvore cuja borda contém apenas letras e , da qual pelo menos letras . Aplicando o mesmo processo à palavranoNÃO+NÃO!bNÃO+NÃO!vsNÃO+NÃO!{\ displaystyle a ^ {N + N!} b ^ {N + N!} c ^ {N + N!}}no{\ displaystyle a}b{\ displaystyle b}NÃO!-NÃO{\ displaystyle N! -N}b{\ displaystyle b}C=noNÃO+NÃO!bNÃOvsNÃO{\ displaystyle w = a ^ {N + N!} b ^ {N} c ^ {N}},obtemos outra árvore de derivação para a mesma palavra . Esta árvore contém uma subárvore cuja borda contém apenas letras e , da qual pelo menos letras . Esta árvore é, portanto, diferente da primeira árvore.noNÃO+NÃO!bNÃO+NÃO!vsNÃO+NÃO!{\ displaystyle a ^ {N + N!} b ^ {N + N!} c ^ {N + N!}}b{\ displaystyle b}vs{\ displaystyle c}NÃO!-NÃO{\ displaystyle N! -N}b{\ displaystyle b}

Demonstração da versão gramatical

Let Ser uma gramática algébrica de variáveis e axiomas . Ou uma palavra que deriva de . G{\ displaystyle G}V{\ displaystyle V}S{\ displaystyle S}C{\ displaystyle w}S{\ displaystyle S}

A prova é simplificada se quisermos apenas estabelecer a versão da linguagem do lema da iteração. Nesse caso, podemos escolher uma gramática na forma normal de Chomsky , e uma árvore de derivação é essencialmente uma árvore binária.

Um lema combinatório

Considere uma árvore na qual certas folhas são distinguidas. Nós dizemos que:

• um nó é distinguido quando a subárvore da qual é a raiz contém folhas distintas;
• um nó é especial quando pelo menos dois de seus filhos são distinguidos.

O pai de um nó distinto é distinguido, a raiz é distinguida assim que uma das folhas é distinguida, um nó especial em si é distinguido.

Uma árvore é de grau se cada nó tiver no máximo filhos. m{\ displaystyle m}m{\ displaystyle m}

Lema  -  Seja uma árvore de grau com folhas distintas. Se cada ramo contiver no máximo nós especiais, então . t{\ displaystyle t}m{\ displaystyle m}k{\ displaystyle k}r{\ displaystyle r}k≤mr{\ displaystyle k \ leq m ^ {r}}

Demonstração

Sim , não há nó especial; há apenas uma folha distinta, pois se houvesse duas, seu ancestral comum seria especial. Suponha , portanto , e deixe ser um nó especial do qual nenhum descendente é especial; cada uma das subárvores de contém no máximo uma folha distinta e, como a no máximo filhos, a árvore raiz contém no máximo folhas distintas. Cada subárvore dessa natureza é agora substituída por uma única folha distinta. O número de nós especiais diminui em 1 em cada ramificação. A árvore obtida possui, por recorrência, no máximo folhas distintas. Como cada uma das novas folhas substituiu uma subárvore com no máximo folhas, isso prova o resultado. r=0{\ displaystyle r = 0}r≥1{\ displaystyle r \ geq 1}x{\ displaystyle x}x{\ displaystyle x}x{\ displaystyle x}m{\ displaystyle m}x{\ displaystyle x}m{\ displaystyle m}mr-1{\ displaystyle m ^ {r-1}}m{\ displaystyle m}

Demonstração

Usamos a contraposição do lema anterior: se a árvore tem folhas estritamente mais distintas, então a árvore tem pelo menos um galho que contém pelo menos nós especiais. mr{\ displaystyle m ^ {r}}1+r{\ displaystyle 1 + r}

Let ser o comprimento máximo dos membros certos das regras. Nós posamos e . Considere uma árvore de derivação para a palavra . Por definição, a árvore é de grau e tem folhas distintas que são as posições distintas de . A árvore tem um galho com pelo menos nós especiais, observou . Cada um desses nós tem pelo menos um filho distinto que não está no ramo; o nó fica à esquerda se esse filho estiver à esquerda do galho, caso contrário , está à direita . Por exemplo , há pelo menos vértices distintos, todos à esquerda ou todos à direita. Como esse número é maior que o número de variáveis, dois vértices e (anotado e na figura), com , são rotulados com a mesma variável . A árvore então dá as derivações m{\ displaystyle m}r=2(|V|+1){\ displaystyle r = 2 (| V | +1)}NÃO=1+mr{\ displaystyle N = 1 + m ^ {r}}C{\ displaystyle w}m{\ displaystyle m}C{\ displaystyle w}1+r{\ displaystyle 1 + r}s0,...,sr{\ displaystyle s_ {0}, \ ldots, s_ {r}}1+r=2|V|+3{\ displaystyle 1 + r = 2 | V | +3}|V|+2{\ displaystyle | V | +2}seu{\ displaystyle s_ {i}}sj{\ displaystyle s_ {j}}b1{\ displaystyle b_ {1}}b2{\ displaystyle b_ {2}}eu<j{\ displaystyle i <j}X{\ displaystyle X}

S→∗xXz{\ displaystyle S {\ stackrel {*} {\ to}} xXz}, e .X→∗vocêXv{\ displaystyle X {\ stackrel {*} {\ to}} uXv}X→∗y{\ displaystyle X {\ stackrel {*} {\ to}} y}

Se os nós distintos são deixados, as palavras contêm posições distintas, caso contrário, as palavras são . Finalmente, se a palavra contém mais do que posições distintas, começamos a divisão novamente a partir da raiz de sua subárvore. x,você,y{\ displaystyle x, u, y}y,v,z{\ displaystyle y, v, z}y{\ displaystyle y}NÃO{\ displaystyle N}sj{\ displaystyle s_ {j}}

Apêndices

Notas e referências

1. Ogden 1968 .
2. Luc Boasson e S. Horváth, “  Sobre as línguas que satifsfying o lema de Ogdens  ”, RAIRO. Ciência da computação teórica , t.  12, n o  3,1978, p.  201-202 ( ler online ).
3. Jean Berstel e Luc Boasson, “Context-Free Languages” , em G. Rozenberg, A. Salomaa (eds), Handbook of Theoretical Computer Science , vol.  B: Modelos formais e semática , Elsevier e MIT Press,1990( ISBN  0-444-88074-7 ) , p.  59-102—Exemplo 2.5, p.  73 .

Bibliografia

• William F. Ogden , "  Um Resultado Útil para Provar Ambiguidade Inerente  " , Teoria de Sistemas Matemáticos , vol.  2 n o  3,1968, p.  191-194 ( DOI  10.1007 / BF01694004 )

• Olivier Carton , linguagens formais, computabilidade e complexidade ,2008[ detalhe da edição ] ( leia online )

• (pt) Marcus Kracht , “  Too Many Languages ​​Satisfy Ogden's Lemma  ” , University of Pennsylvania Working Papers in Linguistics , vol.  10,2004

Artigos relacionados

• Gramática algébrica
• Linguagem algébrica
• Lema de iteração para linguagens algébricas