Contesto libero question language (Pumping Lemma)

Question

So che questo non è direttamente correlata alla programmazione, ma mi chiedevo se qualcuno sa come applicare il lemma di pompaggio al seguente prova:

  

Si dimostri che L = {(a ^ n) (b ^ n) (c ^ m): n = m} non è un linguaggio libero dal contesto

Sono abbastanza fiducioso con l'applicazione lemmi di pompaggio, ma questo è veramente mi irking. Cosa ne pensi?

Answer 1

Modifica: ero totalmente pronti a percorrere la pista sbagliata. Ecco cosa succede quando si tenta di dare una mano quando non hanno completamente risolto il problema io stesso.

Ogden Lemma

L Supponiamo che è contesto libero. Per il lemma di Ogden, esiste un intero p che ha le seguenti proprietà:

Data una stringa w in L almeno lungo simboli p, dove p almeno di quei simboli sono "marcato", w può essere rappresentato come uvxyz, che soddisfano:

1. x ha almeno un marcato simbolo,
2. o uev entrambi hanno segnato simboli o Y e Z hanno segnato entrambi simboli,
3. vxy ha al massimo p segnato dei simboli, e
4. u v ⁱ x y ⁱ z è a L per i> = 0

Questo è il lemma di Ogden. Ora, sia q un numero intero divisibile per ogni intero positivo non superiore p. Sia w = a ^{p + q} b ^{p + q} c ^p . Segnare ogni c. Entro il 2 #, u o v deve contenere almeno un c. Se uno dei due uo V contiene qualsiasi altro simbolo, quindi # 4 non funziona, in modo da u e v deve contenere solo c. Ma poi # 4 non riesce quando i = q / | uv |. Sappiamo che q è divisibile per | uv | perché p> | uv | > 0 e q è divisibile per tutti i numeri interi positivi minore di p.

Si noti che a turno lemma di Ogden nel lemma di pompaggio quando si segnano tutti i simboli.

Pumping Lemma

L Supponiamo che è contesto libero. Dal lemma di pompaggio, c'è una lunghezza p (non necessariamente la stessa p come sopra) in modo che qualsiasi stringa w in L può essere rappresentato come uvxyz, dove

1. | vxy | <= P,
2. | vy | > = 1, e
3. u v ⁱ x y ⁱ z è a L per i> = 0.

Data una stringa w in L, sia m> n o m

Si supponga che m> n. (Si noti che Λ denota la stringa vuota.)

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

Si supponga che n> m.

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

Questo dimostra che nessuna stringa da L fornisce un controesempio utilizzando il lemma di pompaggio per l'ipotesi che L è un linguaggio libero dal contesto (anche se è sensibile al contesto).