Nella teoria dei linguaggi formali il pumping lemma per i linguaggi regolari è una condizione necessaria affinché un linguaggio sia regolare. Viene utilizzato per dimostrare che un linguaggio appartiene ad una classe di linguaggi formali differente da quella generata da grammatiche formali di Tipo 3.
Definizione formale Sia un automa a stati finiti tale che , sia il linguaggio riconosciuto dall'automa e sia tale che ,
È quindi possibile scrivere con e e quindi .
Dimostrazione Sia . Poiché per accettare la stringa z l'automa deve assumere stati (compreso quello iniziale), ma poiché l'automa possiede esattamente n stati distinti, per il principio dei cassetti, uno degli stati (dove è lo stato finale in cui la parola viene riconosciuta) deve comparire almeno due volte.
Si supponga che , ovvero i due stati coincidano nell'insieme Q e sia v la sottostringa di z tale che .
Poiché e , si ha che tutte le stringhe della forma con saranno riconosciute dall'automa, ovvero .
Bibliografia
Voci correlate Pumping lemma per i linguaggi liberi dal contesto
Categoria:Teoria dei linguaggi formali Categoria:Lemmi Categoria:Teoria degli automi