Come a dimostrare che una lingua non è context-free?

https://cs.stackexchange.com/questions/265

16-10-2019
|

Domanda

Abbiamo imparato a conoscere la classe di context-free lingue $ \ mathrm {} CFL $. Essa è caratterizzata da entrambi grammatiche context-free e automi a pila quindi è facile dimostrare che un determinato linguaggio è privo di contesto.

Come posso mostrare il contrario, però? La mia TA è stato fermamente convinto che, al fine di farlo, dovremmo mostrare per tutti grammatiche (o automi) che non possono descrivere la lingua a portata di mano. Questo mi sembra un grande compito!

Ho letto su alcuni di pompaggio lemma ma sembra davvero complicato.

Soluzione

Per quanto ne so il pompaggio lemma è di gran lunga la più semplice e la più utilizzata la tecnica. Se lo trovate duro, provare la versione normale prima, non è poi così male. Ci sono altri mezzi per le lingue che sono lontane dal contesto libero. Per esempio lingue indecidibili sono banalmente non contesto libero.

Detto questo, io sono anche interessati ad altre tecniche che il lemma di pompaggio se ce ne sono.

EDIT: Ecco un esempio per il lemma di pompaggio: supponiamo che il linguaggio di $ L = \ {a ^ k \ metà k ? P \} $ è libera dal contesto ($ P $ è l'insieme dei numeri primi). Il lemma di pompaggio ha un sacco di $ ? / ? $ quantificatori, così farò questo un po 'come un gioco:

Il lemma di pompaggio ti dà un $ p $
dare una parola $ s $ del linguaggio della lunghezza di almeno $ p $
Il lemma di pompaggio riscrive in questo modo: $ s = uvxyz $ con alcune condizioni ($ | vxy | =p $ e $ | VY | =1 $)
Tu dai un intero $ n=0 $
Se $ uv ^ nxy ^ nz $ non è in $ L $, si vince, $ L $ non è libera dal contesto.

Per questo particolare linguaggio a $ s $ ogni $ a ^ k $ (con $ k=p $ e $ k $ è un numero primo) farà il trucco. Poi il lemma di pompaggio ti dà $ Uvxyz $ con $ | Vy | =1 $. Fare confutare la contesto-gratuità, è necessario trovare $ n $ tale che $ | uv ^ nxy ^ nz |. $ non è un numero primo

$$ | uv ^ nxy ^ nz | = | e | + (n-1) | vy | = k + (n-1) | Vy | $$

E poi $ n = k + 1 $ farà: $ K + K | vy | = k (1 + | Vy |) $ non è primo in modo da $ uv ^ nxy ^ nz \ Non \ in L $. Il lemma di pompaggio non può essere applicato in modo $ L $ non è libera dal contesto.

Un secondo esempio è la lingua $ \ {ww \ mid w \ in \ {a, b \} ^ {\ ast} \} $. Noi (ovviamente) dobbiamo scegliere una stringa e mostrare che non c'è modo possibile, può essere suddiviso in quei cinque parti e hanno ogni corda derivato pompato rimanere nella lingua.

La stringa $ s = a ^ {} p b ^ {p} a ^ {p} b ^ {p} $ è una scelta adatta per questa dimostrazione. Ora non ci resta che guardare dove $ V $ e $ y $ possono essere. Le parti principali sono che $ v $ o $ y $ deve avere qualcosa in esso (forse entrambi), e che entrambi $ v $ e $ y $ (e $ x $) sono contenuti in una lunghezza $ p $ sottostringa - così essi non possono essere troppo distanti.

Questa stringa ha un certo numero di possibilità per cui $ v $ e $ y $ potrebbero essere, ma si scopre che molti dei casi in realtà sembrano piuttosto simili.

$ Vy \ in un ^ {\ ast} $ o $ Vy \ in b ^ {\ ast} $. Allora sono entrambi contenuti in una delle sezioni di $ contigua un $ s o $ b $ s. Questo è il caso relativamente facile da sostenere, come che tipo di non importa quale sono in supponga che $ |. Vy | = K \ leq p $.
- Se sono nella prima sezione di $ a $ s, poi quando abbiamo pompa, la prima metà della nuova stringa è $ a ^ {p + k} b ^ {pk / 2} $, e il secondo è $ b ^ {/ 2 k} a ^ {} p b ^ {p} $. Ovviamente questo non è di forma $ ww $.
- L'argomento per una qualsiasi delle altre tre piste sezioni più o meno lo stesso, è proprio dove il $ k $ e $ k / 2 $ finisce nella indici.
$ vxy $ a cavallo tra due delle sezioni. In questo caso di pompaggio giù è tuo amico. Anche in questo caso ci sono molti posti in cui questo può accadere (3 per l'esattezza), ma mi limiterò a fare uno uno illustrativo, e il resto dovrebbe essere facile da capire da lì.
- Si supponga che $ vxy $ a cavallo del confine tra il primo $ una sezione $ ed il primo $ b $ sezione. Sia $ vy = a ^ {k_ {1}} b ^ {k_ {2}} $ (non importa proprio dove il $ a $ s e $ b $ s sono in $ v $ e $ y $, ma sappiamo che sono in ordine). Poi, quando abbiamo pump down (ovvero il $ i = 0 $ caso), otteniamo la nuova stringa $ s'= a ^ {p-k_ {1}} b ^ {p-k_ {2}} a ^ {p} b ^ {p} $, ma poi se $ s'$ potrebbe essere diviso in $ ww $, il punto medio deve essere in qualche parte del secondo $ una sezione $, quindi la prima metà è $ a ^ {p-k_ {1} } b ^ {p-k_ {2}} {a ^ (k_ {1} + k_ {2}) / 2} $, e la seconda metà è un $ ^ {p- (k_ {1} + k_ {2 }) / 2} b ^ {p} $. Chiaramente questi non sono la stessa stringa, quindi non possiamo mettere $ v $ und $ y $ lì.

I restanti casi dovrebbe essere abbastanza trasparente da lì - sono le stesse idee, solo mettendo $ v $ e $ y $ negli altri 3 punti in prima istanza, e 2 punti in seconda istanza. In tutti i casi però, si può pompare in modo tale che l'ordinamento è chiaramente incasinato quando si divide la stringa in due.

Altri suggerimenti

Ogden Lemma

Lemma (Ogden). Let $ L $ un linguaggio context-free. Poi v'è una costante $ n $ tale che per ogni $ z \ in L $ e qualsiasi modo di marcatura $ N $ o più posizioni (simboli) di $ z $ come "posizioni distinte", allora $ Z $ può essere scritta da $ z = uvwxy $, in modo tale che

$ VX $ ha almeno una posizione distinta.

$ VWX $ ha al massimo $ N $ distingue posizioni.

Per tutti i $ \ GEQ 0 $, $ uv ^ IWx ^ iy \ in L $.

Esempio Sia $ L = \ {a ^ ib ^ jc ^ K: \ neq j, j \ neq k, i \ neq k \}. $. Si assuma $ L $ è context-free, e lasciare che $ N $ essere la costante data dal lemma di Ogden. Sia $ z = a ^ Nb ^ {N + N!} C ^ {N + 2N!} $ (Che appartiene a $ L $), e supponiamo che marchio come distinto tutte le posizioni del simbolo $ a $ (cioè il primo $ N $ posizioni di $ z $). Diamo $ z = uvwxy $ essere una decomposizione di $ z soddisfare le condizioni da lemma di Ogden $.

Se $ v $ o $ x $ contengono simboli differenti, allora $ uv ^ ^ 2wx 2y \ notin L $, perché non ci saranno simboli nell'ordine sbagliato.
Almeno uno dei $ v $ e $ x $ deve contenere solo simboli $ A $, perché s solo il $ A $ 'sono stati distinti. Così, se $ x \ a L (b ^ *) $ o $ x \ a L (c ^ *) $, quindi $ v \ a L (A + ^) $. Sia $ p = | v | $. Poi $ 1 \ leq p \ leq N $, il che significa che $ P $ divide $ N! $. Sia $ q = N! / P $. Poi $ z '= uv ^ {2q + 1} wx ^ {2q + 1} y $ deve appartenere $ L $. Tuttavia, $ v ^ {2q + 1} = a ^ {2pq + p} = a ^ {2N! + P} $. Dal momento che $ $ uwy ha esattamente $ N-P $ simboli $ A $, allora $ z '$ ha $ 2N! + N simboli $ $ A $. Ma entrambi $ v $ e $ x $ non hanno $ c $ 's, in modo da $ z' $ ha anche $ 2N! + N simboli $ $ C $, il che significa che $ z '\ notin L $, e questo contraddice lemma di Ogden. Una contraddizione simile si verifica se $ x \ a L (A ^ +) $ o $ x \ a L (c ^ *) $. Concludiamo $ L $ non è context-free.

Esercizio Utilizzo Lemma di Ogden, spettacolo che $ L = \ {a ^ ib ^ jc ^ kd ^ {\ ell}:. I = 0 \ text {o} j = k = \ ell \} $ non è context-free.

Pumping Lemma

Questo è un caso particolare del lemma di Ogden in cui si distinguono tutte le posizioni.

Lemma. Let $ L $ un linguaggio context-free. Poi v'è una costante $ n $ tale che per ogni $ z \ in L $, $ z $ può essere scritta da $ z = uvwxy $, in modo tale che

$ | VX |> 0 $
.
$ | VWX |. \ Leq N $

Per tutti i $ \ GEQ 0 $, $ uv ^ IWx ^ iy \ in L $.

Parikh è Teorema

Questo è ancora più tecnico che Lemma di Ogden.

Definizione. Let $ \ Sigma = \ {a_1, \ ldots, a_n \} $. Definiamo $ \ Psi _ {\ sigma}: \ Sigma ^ * \ to \ mathbb {N} ^ n $ da $$ \ Psi _ {\ Sigma} (w) = (m_1, \ ldots, M_n), $$ dove $ m_i $ è il numero di presenze di $ A_i $ a $ w $.

Definizione Un sottoinsieme $ S $ di $ \ mathbb {N} ^ n $ è chiamato linear se può essere scritto.: $$ S = \ {\ mathbf {u_0} + \ sum_ {1 \ le i \ le k} A_i \ mathbf {u_i}: \ text {per un insieme di $ \ mathbf {u_i} \ in \ mathbb {N} ^ n $ e $ A_i \ in \ mathbb {N} $} \} $$

Definizione. Un sottoinsieme $ S $ di $ \ mathbb {N} ^ n $ è chiamato semi-linear se è l'unione di un insieme finito di lineari set.

Teorema (Parikh). Let $ L $ un linguaggio di più di $ \ Sigma $. Se $ L $ è context-free, quindi $$ \ Psi _ {\ Sigma} [L] = \ {\ Psi _ {\ Sigma} (w): w \ in L \}. $$ è semi-linear

Esercizio Utilizzo Teorema di Parikh, spettacolo che $ L = \ {0 ^ m1 ^ n. M> n \ text {o} (m \ text {è primo e} m \ leq n ) \} $ non è context-free.

Esercizio. Utilizzo Teorema di Parikh, spettacolo che ogni linguaggio context-free su un alfabeto unario è anche normale.

proprietà di chiusura

chiusura

Una volta che avete una piccola collezione di linguaggi liberi dal contesto non è spesso possibile utilizzare proprietà di $ \ mathrm {} CFL $ in questo modo:

Si supponga $ L \ in \ mathrm {} CFL $. Poi, dalla chiusura di proprietà X (insieme a Y), $ L' \ in \ mathrm {} CFL $. Questo contraddice $ L' \ notin \ mathrm {} CFL $ che sappiamo attesa, quindi $ L \ notin \ mathrm {} CFL $.

Questo è spesso più brevi (e spesso meno soggetto a errori) che utilizza uno degli altri risultati che utilizzano meno conoscenza preventiva. E 'anche un concetto generale che può essere applicato tutti i tipi di classe di oggetti.

Esempio 1: intersezione con regolari Languages ??

Si segnala $ \ L mathcal (e) $ il linguaggio regolare specificato da un'espressione regolare $ e $.

Sia $ L = \ {w \ mid w \ in \ {a, b, c \} ^ *, | w | _a = | w | _b = | w | _c \} $. Come

$ \ qquad \ displaystyle L \ cappello \ mathcal {L} (a ^ * b ^ * c ^ *) = \ {a ^ nb ^ nc ^ n \ mid n \ in \ mathbb {N} \} \ notin \ mathrm {} CFL $

e $ \ mathrm {} CFL $ è chiuso sotto all'incrocio con linguaggi regolari, $ L \ notin \ mathrm {} CFL $.

Esempio 2: (Inverse) homomorphism

Sia $ L = \ {(ab) ^ {2n} c ^ MD ^ {2n-m} (ABA) ^ {n} \ metà m, n \ in \ mathbb {N} \} $. Con l'omomorfismo

$ \ qquad \ displaystyle \ phi (x) = \ begin {casi} un & x = a \\ \ Varepsilon & x = b \\ b & x = c \ lor x = d \ End {casi} $

abbiamo $ \ phi (L) = \ {a ^ {2n} b ^ {2n} a ^ {2n} \ mid n \ in \ mathbb {N} \}. $

Ora, con

$ \ qquad \ displaystyle \ psi (x) = \ begin {casi} AA & x = a \ lor x = c \\ bb & x = b \ end {cases} \ quad \ text {e} \ quad L_1 = \ {x ^ nb ^ ny ^ n \ intermedio x, y \ in \ {a, c \} \ cuneo n \ in \ mathbb {N} \ }, $

otteniamo $ L_1 = \ psi ^. {- 1} (\ phi (L))) $

Infine, intersecando $ L_1 $ con il linguaggio regolare $ L_2 = \ mathcal L (a ^ * b ^ * c ^ *) $ otteniamo la lingua $ L_3 = \ {a ^ nb ^ nc ^ n \ mid n \ in \ mathbb {N} \} $.

In totale, abbiamo $ L_3 = L_2 \ cappello \ psi ^ {- 1}. (\ Phi (L)) $

Ora supponiamo che $ L $ è context-free. Poi, dal momento che $ \ mathrm {} CFL $ è chiuso contro omomorfismo, homomorphism inversa, e intersezione con set regolari, $ L_3 $ è context-free, anche. Ma noi sappiamo (via Pumping Lemma, se necessario) che $ L_3 $ non è context-free, quindi questa è una contraddizione; abbiamo dimostrato che $ L \ notin \ mathrm {} CFL $.

Interchange Lemma

Interchange lemma [1] propone una condizione necessaria per il contesto-freeness che è ancora più forte di di Ogden Lemma . Ad esempio, può essere usato per mostrare che

$ \ qquad \ {xyyz \ metà x, y, z \ in \ {a, b, c \} ^ + \} \ notin \ mathrm {} CFL $

che resiste molti altri metodi. Questo è il lemma:

Sia $ L \ in \ mathrm {} CFL $. Poi v'è una costante $ c_L $ tale che per ogni intero $ n \ geq 2 $, qualsiasi insieme $ Q_n \ subseteq L_n = L \ cap \ Sigma ^ n $ e ogni intero $ m $ con $ n \ geq m \ geq 2 $ non ci sono $ k \ geq \ frac {| Q_n |} {c_L n ^ 2} $ stringhe $ z_i \ in Q_n $ con

$ z_i = w_ix_iy_i $ per $ i = 1, \ dots, k $,

$ | W_1 | = | W_2 | = \ Puntini = | w_k | $,

$ | y_1 | = | Y_2 | = \ dots = | y_k | $,

$ m \ geq | x_1 | = | X_2 | = \ dots = | x_k | > \ Frac {m} {2} $ e

$ w_ix_jy_i \ in L_n $ per tutti i $ (i, j) \ in [1..k] ^ 2 $.

L'applicazione significa trovare $ n, m $ e $ Q_n $ tale che 1.-4. hold ma 5. è violata. L'esempio di applicazione proposta nel documento originale è molto dettagliata e viene quindi lasciata qui.

In questo momento, non ho un punto di riferimento liberamente disponibili e la formulazione di cui sopra è tratto da un preprint di [1] dal 1981. Ho apprezzato aiuto nel rintracciare riferimenti migliori. Sembra che la stessa proprietà è stata (ri) scoperto di recente [2].

altre condizioni necessarie

Boonyavatana e Slutzki [3] di indagine diverse condizioni simiLAR al pompaggio e di interscambio Lemma.

Un “Interchange Lemma” per il contesto-Gratis Lingue da W. Ogden, RJ Ross e K. Winklmann (1985)
Swapping Lemmi per regolare e Context-free Lingue di T. Yamakami (2008)
Lo scambio o la pompa (DI) lemmi per linguaggi context-free di R. Boonyavatana e G. Slutzki (1988)

Non v'è alcun metodo generale dal momento che i set non-libero context-lingue non è semi-decidibile (anche noto come R.E.). Se ci fosse un metodo generale, potremmo usiamo per semi-decidere questo set.

La situazione è ancora peggiore, in quanto dato due CFL non è possibile decidere se la loro intersezione è anche un CFL.

Riferimento:. Hopcroft e Ullman, "Introduzione alla teoria degli automi, Lingue, and Computation" 1979

Una versione più forte della condizione del Ogden ( OC ) è il

condizioni di Bader-Moura (BMC)

Un linguaggio $ L \ subseteq \ Sigma ^ * $ soddisfa BMC se esiste una costante $ n $ tale che se $ z \ in L $ e abbiamo etichetta in essa "distinto" posizioni $ d (z) $ e $ e (z) $ posizioni "esclusi", con $ d (z)> n ^ {e (z) +1} $, allora possiamo scrivere $ z = uvwxy $ tale che:

$ d (VX) \ geq 1 $ e $ e (VX) = 0 $

$ d (VWX) \ leq n ^ {e (VWX) +1} $ e

per ogni $ i \ GEQ 0 $, $ uv ^ IWx ^ iy $ è in $ L $.

Si dice che una lingua $ L \ a BMC (\ Sigma) $ se $ L $ soddisfa le condizioni del Bader-Moura.

Abbiamo $ CFL (\ Sigma) \ subset BMC (\ Sigma) \ subset OC (\ Sigma) $, in modo da BMC è strettamente più forte di OC.

Riferimento: Bader, C., Moura, A., una generalizzazione del Lemma di Ogden. JACM 29, n. 2, (1982), 404-407

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a cs.stackexchange