Dsy Network www | forum | my | didattica | howto | wiki | el goog | stats | blog | dona | rappresentanti
Homepage
 Register   Calendar   Members  Faq   Search  Logout 
.dsy:it. : Powered by vBulletin version 2.3.1 .dsy:it. > Didattica > Corsi G - M > Linguaggi formali e automi > Linguaggi e traduttori - Pumping lemma
  Last Thread   Next Thread
Author
Thread    Post New Thread    Post A Reply
vfldj
.simpatizzante.

User info:
Registered: Mar 2013
Posts: 11 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 0:53:14 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged
Linguaggi e traduttori - 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è 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.

19-08-2013 19:26
Click Here to See the Profile for vfldj Click here to Send vfldj a Private Message Find more posts by vfldj Add vfldj to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 09:57.    Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread | Add to Bookmarks

Forum Jump:
Rate This Thread:

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
 

Powered by: vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento | Licenze | Thanks | Syndacate
Pagina generata in 0.044 seconds (49.86% PHP - 50.14% MySQL) con 30 query.