PUMPING LEMMA

è una condizione necessaria (ma non sufficiente) per dimostrare che un linguaggio è di tipo 2 o di tipo 3, si basa sul concetto che in un linguaggio infinito a un certo punto deve essere presente una stringa motore che viene ripetuta $n$ volte (pompata) per ottenere nuove stringhe del linguaggio

Se $L$ e un linguaggio di tipo 2 esiste un intero $N$ tale che per ogni stringa $z:len(z)\ge N$ per cui:

• $z$ e scomponibile in 5 parti $z=uvwxy$
• $vwx\le N$
• $|vx|\ge 1$

Dove le componenti $v$ $x$ possono essere ripetute (pompate) per ottenere le altre frasi del linguaggio

$u{v}^{i}w{x}^{i}y\in L\forall i\ge 0$

LINGUAGGI DI TIPO 3

Esiste una variante del teorema per linguaggi di tipo 3

Se $L$ e un linguaggio di tipo 3 esiste un intero $N$ tale che per ogni stringa $z:len(z)\ge N$ per cui:

• $z$ e scomponibile in 3 parti $z=xyw$
• $y\le N$
• $|y|\ge 1$

Dove la componente centrale $y$ può essere ripetuta (pompata) per ottenere le altre frasi del linguaggio

$x{y}^{i}w\in L\forall i\ge 0$

PREVIOUS NEXT