Corretta applicazione del CFL Pumping Lemma

Aug 16 2020

Mi sono imbattuto in questa domanda sul mostrare che la lingua $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$è contestuale ma non lineare nel libro di Peter Linz. Ciò è facilmente realizzabile dal lemma di pompaggio separato per i linguaggi lineari (come indicato nel libro di Linz), ma la mia domanda è diversa.

Evidentemente questo è un CFL, e per esso può essere costruito un automa pushdown. Ma se applico il lemma di pompaggio per le CFL, trovo che sono in grado di pompare stringhe che non appartengono alla lingua, il che significherebbe che la lingua non è una CFL. Chiaramente sto facendo qualcosa di sbagliato.

Seguendo il formato "simile a un gioco" fornito a Linz, diciamo di scegliere $w = a^mb^mc^{2m}$, $|w| \ge m$. L'avversario può scegliere una serie di scomposizioni$w = uvxyz$, possono assomigliare a -:

  • $v = a^k, y = a^l$: Il caso in cui $|vxy|$ è contenuto all'interno di $a$è della stringa. Pompa$i = 0$, e poi $w_0 = a^{m – (k + l)}b^mc^{2m}$ non può essere nella lingua poiché l'uguaglianza non è più valida.
  • $v = a^k, y = b^l$: Il caso in cui $v$ è nel $a$ sezione, $x$ si estende su $a$è e $b$è, e $y$ è nel $b$sezione. Ancora una volta, pompa$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ non può essere nella lingua.

Ci sono più casi come questi. Dove sbaglio nell'applicazione della CFL PL?

Risposte

1 vonbrand Aug 17 2020 at 08:20

Il lemma di pompaggio per CFL afferma che se $L$ è una CFL, esiste una costante $N \ge 1$ tale che per tutti $\omega \in L$ con $\lvert \omega \rvert \ge N$ c'è una divisione $\sigma = u v w x y$ con $\lvert v w x \rvert \le N$ e $v x \ne \varepsilon$ tale che $u v^k w x^k y \in L$ per tutti $k \ge 0$.

(Il lemma di pompaggio per le lingue normali è simile, la discussione seguente si applica con piccole modifiche).

Lo vuoi dimostrare per contraddizione $L$non è una CFL. Quindi presumi$L$è una CFL e crea una contraddizione con il lemma. Ciò significa, in dettaglio:

  • Come $L$è una CFL, soddisfa il lemma. In particolare, c'è una costante$N$ tale che ...
  • Poiché il lemma afferma tutte le stringhe lunghe in$L$ può essere diviso, sei libero di sceglierne uno con cui è facile lavorare.
  • Il lemma afferma che esiste una divisione di$\omega$tale che .... per tutti $k \ge 0$...; per contraddire il lemma devi dimostrare che nessuna divisione funziona. In pratica, prendi una determinata divisione del tuo$\omega$( qualsiasi divisione) e sceglierne alcuni$k$per quello che non fornisce una stringa nella lingua. Potrebbe essere necessario dividerlo in casi.

Cosa succede per le stringhe che non appartengono alla lingua o sono più brevi di $N$, è completamente irrilevante. Potrebbe essere che alcune stringhe possano essere pompate, che alcuni valori di$k$funziona per tutte le stringhe, ... Ciò che è cruciale è che per una stringa$\omega$(quello che hai scelto) nessuna divisione funziona con un valore di$k$(di nuovo, quello che hai scelto). Come afferma il lemma, funziona per tutte le stringhe abbastanza lunghe, con una divisione per tutte $k$, un controesempio è sufficiente. Infiniti esempi non provano nulla.