Ieri siamo andati a parlare con il prof Calzavara e abbiamo raccolto un'importante indicazione sull'applicazione del pumping lemma.
- Non fare l'errore di applicare il PL a un esempio, "dimenticandosi" di includere la lunghezza p nella dimostrazione.
Per esempio, la soluzione di 1.49/b non può essere di prendere una stringa 1111010101... perché presuppone che p≤4, ma non prova niente nel caso in cui p>4.
Un'idea di fondo più "solida" sarebbe dire che abbiamo una stringa 1p01p che sicuramente è più lunga di p, e la cui parte sinistra sia xy, mentre z è la parte a destra dello zero. Facendo il pumping up si arriva ad avere un numero di 1 a sinistra maggiore del numero di 1 a destra, che contraddice la definizione del linguaggio.
- Il costrutto contrario di "per tutti esiste uno" è "per qualcuno non esiste nessuno".
Non è sufficiente trovare un caso in cui qualcosa non funziona, ma bisogna trovare un caso in cui niente funziona.
- In ogni caso, quando si parla di pumping lemma più che dividere la stringa in tre parti è meglio valutare se dividerla in una "parte sinistra" pompabile e una parte destra.
Più che cercare di definire quale sia la suddivisione in xyz, è meglio definire le caratteristiche che dovrebbe avere questa suddivisione.
- Il pumping lemma nei linguaggi context-free è più complicato, perché non c'è più una "parte sinistra" pompabile, ma c'è una suddivisione in cinque della stringa per cui la zona pompabile diventa quella centrale.