Lingua degli elenchi di parole, non tutti sono diversi, non è senza contesto

Question

Come dimostrare che la lingua seguente non è priva di contesto utilizzando il lemma del pompaggio? $$ L={w_1 \ # w_2 \ # \ dots \ #w_k \ colon k ≥ 2, w_i \ in \ {0,1 \} ^ *, w_i= w_j \ text {per alcuni} I \ ne j \} $$

Ho problemi a scegliere la stringa da usare per la prova.So che devo scegliere una stringa tale che almeno due sottostringhe separate dal # sono uguali l'una all'altra ma non sono sicure di come avvicinarsi a questo.Se qualcuno potrebbe aiutarmi con questo, lo apprezzerei.

Answer 1

Se $ l $ è stato senza contesto, quindi sarebbe $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ Be, dove $ d $ è l'omomorfismo che cancella $ \ # $ .Tuttavia, $ l '$ è la lingua dei quadrati (parole del modulo $ w ^ 2 $ ), che è ben noto di non essere senza contesto.

Se per qualche motivo devi dimostrare che $ l $ non è senza contesto direttamente utilizzando il lemma del pompaggio, questo suggerisce di esaminare la prova che $ L '$ non è senza contesto e cercando di adattarlo.