Pumping Lemma e linguaggi regolari

Messaggioda clockover » 23/01/2009, 15:14

Sto cercando di capire come dimostrare la non regolarità di un linguaggio attraverso il Pumping Lemma

ora prendo come esempio un linguaggio $L = {a^n b^m c^n | n >= 0, m>= 0}$

Per il teorema
Per ogni linguaggio regolare $L$ esiste una costante $n$ tale che se $z in L$ e $|z| >= n$ allora possiamo scrivere $z = uvw$, con $|uv| <= n$, $|v| >= 1$ e ottenere che $uv^iw in L$ per ogni $i >= 0$

Dovrei dunque dimostrare, supponendo che $L$ sia regolare, la non regolarità! Essendo una condizione necessaria mi basterà dimostrare che il teorema non è soddisfatto e sono a cavallo!
Il problema è che non ho mica capito come fare... non so neanche come cominciare! Avrei bisogno di una mano se qualcuno può!

Grazie in anticipo!
Avatar utente
clockover
Junior Member
Junior Member
 
Messaggio: 179 di 247
Iscritto il: 02/09/2008, 10:08

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite