Contexto Gratis Idioma Pregunta (Bombeo Lema)

Question

Sé que esto no está directamente relacionada con la programación, pero me preguntaba si conocen a alguien cómo aplicar el lema de bombeo para la siguiente prueba:

  

Demostrar que L = {(a ^ n) (b ^ n) (c ^ m): n = m} no es un lenguaje libre de contexto

Estoy bastante seguro con la aplicación de los lemas de bombeo, pero éste me está molestando. ¿Qué opinas?

Answer 1

Edit: Yo estaba totalmente que le conduce por el camino equivocado. Es lo que pasa cuando trato de ayudar al equipo cuando no he resuelto completamente el problema mismo.

Lema de Ogden

Supongamos que L es libre de contexto. Por el lema de Ogden, existe un p entero que tiene las siguientes propiedades:

Dada una cadena w en L al menos p símbolos largo, donde al menos p de estos símbolos son "marcado", w puede ser representado como uvxyz, que satisfacen:

1. x tiene al menos una marcada símbolo,
2. ya sea u y v ambos han marcado símbolos o Y y Z ambos han marcado símbolos,
3. vxy tiene en la mayoría de los símbolos p marcada, y
4. u v ⁱ x y ⁱ z está en L para i> = 0

Ese es el lema de Ogden. Ahora, vamos q sea un número entero divisible por cada número entero positivo no mayor que p. Sea w = a ^{p + q} b ^{p + q} c ^p . Marcar todos los c. Por # 2, U o V debe contener al menos un c. Si U o V contiene cualquier otro símbolo, a continuación, # 4 no funciona, por lo que u y v debe contener sólo c. Pero entonces # 4 falla cuando i = q / | uv |. Sabemos q es divisible por | uv | porque p> | uv | > 0, y q es divisible por todos los números enteros positivos menores que p.

Tenga en cuenta que las vueltas lema de Ogden en el lema de bombeo cuando se marcan todos los símbolos.

Bombeo Lema

Supongamos que L es libre de contexto. Por el lema de bombeo, hay una longitud p (no necesariamente el mismo p como anteriormente) de tal manera que cualquier cadena w en L se puede representar como uvxyz, donde

1. | vxy | <= P,
2. | Vy | > = 1, y
3. u v ⁱ x y ⁱ z está en L para i> = 0.

Dada una cadena w en L, ya sea m> n o m

Supongamos que m> n. (Tenga en cuenta que Λ denota la cadena vacía.)

• Sea u = a ⁿ b ⁿ c ^m-1
• Sea v = c
• Sea x = Λ
• Sea y = Λ
• Sea z = Λ

Supongamos que n> m.

• Sea u = a ^n-1
• Sea v = a
• Sea x = Λ
• Sea y = b
• Let z = b ^n-1 c ^m

Esto demuestra que no hay cadena de L proporciona un contraejemplo usando el lema de bombeo para el supuesto de que L es un lenguaje libre de contexto (a pesar de que es sensible al contexto).