Pergunta de linguagem livre de contexto (bombeamento de lema)

Question

Sei que isso não está diretamente relacionado à programação, mas eu queria saber se alguém sabe como aplicar o lema de bombeamento à seguinte prova:

Mostre isso L = {(a^n) (b^n) (c^m): n! = M} não é uma linguagem livre de contexto

Estou bastante confiante em aplicar lemas de bombeamento, mas este está realmente me irrita. O que você acha?

Answer 1

EDIT: Eu estava liderando totalmente você na pista errada. É o que acontece quando tento ajudar quando não resolvi completamente o problema.

Lema de Ogden

Suponha que L seja livre de contexto. Pelo lema de Ogden, existe um número inteiro P que possui as seguintes propriedades:

Dada uma corda w em l pelo menos símbolos P por muito tempo, onde pelo menos P desses símbolos estão "marcados", W pode ser representado como Uvxyz, que satisfaz:

1. x tem pelo menos um símbolo marcado,
2. u e v ambos têm símbolos marcados ou y e z têm símbolos marcados,
3. Vxy tem no máximo s símbolos marcados e
4. UV^eu XY^eu z está em l para i> = 0

Esse é o lema de Ogden. Agora, seja q um número inteiro divisível por todo número inteiro positivo não maior que p. Seja w = a^p+q b^p+q c^p. Marque cada c. Por #2, u ou v devem conter pelo menos um c. Se u ou v contiver qualquer outro símbolo, então o #4 falhará, para que u e v devem conter apenas c. Mas então o #4 falha quando i = Q/| UV |. Sabemos que q é divisível por | UV | Porque p> | uv | > 0, e Q é divisível por todos os números inteiros positivos menores que p.

Observe que o lema de Ogden se transforma no lema de bombeamento quando você marca todos os símbolos.

Lema de bombeamento

Suponha que L seja livre de contexto. Pelo lema de bombeamento, há um comprimento P (não necessariamente o mesmo p que acima), de modo que qualquer corda w em l possa ser representada como uvxyz, onde

1. | vxy | <= P,
2. | vy | > = 1 e
3. UV^eu XY^eu Z está em L para i> = 0.

Dada uma corda w em l, m> n ou m <n. Suponha que p = 2.

Suponha que m> n. (Observe que λ indica a corda vazia.)

• Deixe você = aⁿ bⁿ c^M-1
• Deixe v = c
• Seja x = λ
• Deixe y = λ
• Seja z = λ

Suponha que n> m.

• Deixe você = a^N-1
• Deixe v = a
• Seja x = λ
• Deixe y = B
• Deixe Z = B^N-1 c^m

Isso demonstra que nenhuma corda de L fornece um contra -exemplo usando o lema de bombeamento para a suposição de que L é uma linguagem livre de contexto (mesmo que seja sensível ao contexto).