Pumping lemma
Ciao, sono giorni che studio il pumping lemma ma ancora non mi è chiaro.
So che ci sono due tipi di pumping lemma: quello per i linguaggi regolari e quello per i linguaggi context-free.
Il primo mi dice che se pompo la $w$ in $uwv$ (cioè $uw^iv$), la stringa ottenuta appartiene ancora al linguaggio.
Se il pumping lemma vale allora non si può dire nulla su L mentre se non vale allora L non è regolare.
Il secondo mi dice che se pompo $u$ e $v$ in $uwv$ (cioè $u^iwv^i$), la stringa ottenuta appartiene ancora al linguaggio.
Se il pumping lemma vale allora non si può dire nulla su L mentre se non vale allora L non è context-free.
Dato $L={ab^nc^mb^n | n,m>0}$ devo dire se è regolare, context-free o nessuno dei due e in ogni caso devo dimostrarlo con il pumping lemma.
Io lo farei in questo modo
http://img829.imageshack.us/img829/5125/akcf.jpg
E avanti così per tutti i casi, alla fine ottengo che è non è non regolare (cioè non posso dire nulla sul linguaggio) poichè nel primo caso il pumping lemma è valido. Eppure io so, grazie alle soluzioni, che quel linguaggio non è regolare ma è context-free quindi il mio procedimento è sbagliato.
Per dimostrare che è context-free applicherei il pumping lemma nello stesso modo però pompando $u$ e $v$ e guarderei se il pumping lemma è valido, se non lo è vuol dire che non è context-free, altrimenti si (ma in realtà se il pumping lemma è valido, non posso dire che il linguaggio sia context-free). Allora come faccio a dimostrare che è context-free?
E poi, quando pompo $u$ e $v$, queste vengono "elevate a $i$" ma la $i$ è la stessa o può essere differente?
Per esempio, nel caso 2 del disegno, supponendo di usare il pumping lemma per i linguaggi context-free, pompando $u$ e $v$ ottengo stringhe del tipo aaabbbccb (ho considerato $i=3$ quindi la stringa diventa $a^3b^3ccb$) oppure abbbccb (ho considerato $i_1=1$ e $i_2=3$ quindi la stringa diventa $ab^3ccb$)?
Troppi dubbi..
Grazie.
So che ci sono due tipi di pumping lemma: quello per i linguaggi regolari e quello per i linguaggi context-free.
Il primo mi dice che se pompo la $w$ in $uwv$ (cioè $uw^iv$), la stringa ottenuta appartiene ancora al linguaggio.
Se il pumping lemma vale allora non si può dire nulla su L mentre se non vale allora L non è regolare.
Il secondo mi dice che se pompo $u$ e $v$ in $uwv$ (cioè $u^iwv^i$), la stringa ottenuta appartiene ancora al linguaggio.
Se il pumping lemma vale allora non si può dire nulla su L mentre se non vale allora L non è context-free.
Dato $L={ab^nc^mb^n | n,m>0}$ devo dire se è regolare, context-free o nessuno dei due e in ogni caso devo dimostrarlo con il pumping lemma.
Io lo farei in questo modo
http://img829.imageshack.us/img829/5125/akcf.jpg
E avanti così per tutti i casi, alla fine ottengo che è non è non regolare (cioè non posso dire nulla sul linguaggio) poichè nel primo caso il pumping lemma è valido. Eppure io so, grazie alle soluzioni, che quel linguaggio non è regolare ma è context-free quindi il mio procedimento è sbagliato.
Per dimostrare che è context-free applicherei il pumping lemma nello stesso modo però pompando $u$ e $v$ e guarderei se il pumping lemma è valido, se non lo è vuol dire che non è context-free, altrimenti si (ma in realtà se il pumping lemma è valido, non posso dire che il linguaggio sia context-free). Allora come faccio a dimostrare che è context-free?
E poi, quando pompo $u$ e $v$, queste vengono "elevate a $i$" ma la $i$ è la stessa o può essere differente?
Per esempio, nel caso 2 del disegno, supponendo di usare il pumping lemma per i linguaggi context-free, pompando $u$ e $v$ ottengo stringhe del tipo aaabbbccb (ho considerato $i=3$ quindi la stringa diventa $a^3b^3ccb$) oppure abbbccb (ho considerato $i_1=1$ e $i_2=3$ quindi la stringa diventa $ab^3ccb$)?
Troppi dubbi..
Grazie.
Risposte
Qualcuno sa aiutarmi? 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
