Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pumping Lemma per i linguaggi context-free - Coggle Diagram
Pumping Lemma per i linguaggi context-free
Vale per i
linguaggi CF
Non serve a dimostrare che un linguaggio è CF
Serve invece per dimostrare che un linguaggio non è CF
Se un linguaggio è CF
Allora esiste una
lunghezza di pumping
Se prendo una stringa del linguaggi abbastanza lunga
Con lunghezza almeno p
Allora la stringa si può dividere in 5 parti:
s = uvxyz
Se
s = uvxyz
, devono valere queste 3 condizioni:
Per ogni i >= 0, $$uv^ixy^iz \in A$$
$$|vy| > 0$$
$$|vxy| \le p$$
Se una stringa è molto lunga
Il suo albero sintattico deve essere alto
Se l'albero è molto alto lungo un cammino
Comparirà due volte lo stesso NT
Quindi si formano due sottoalberi simili
Questo permette di copiare o tagliere una parte dell'albero
Nella stringa finale i pezzi v e y possono essere pompati
Si usa quasi sempre per
assurdo
Si suppone che il linguaggio sia CF
Allora deve valere il pumping lemma
Scelgo una stringa lunga adatta
Considero tutte le possibili divisioni
uvxyz
Si mostra che pompando con qualche valore di
i
la stringa esce dal linguaggio
Si ottiene l'assurdo
Quindi il linguaggio non è CF