Linguaggi e traduttori - Pumping lemma
Clicca QUI per vedere il messaggio nel forum |
| vfldj |
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è uwiv), 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è uiwvi), 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={abncmbn|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 a3b3b) oppure abbbccb (ho considerato i1=1 e i2=3 quindi la stringa diventa ab3b)?
Troppi dubbi..
Grazie. |
|
|
|
