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 > Help pumping lemma
Pages (2): « 1 [2]   Last Thread   Next Thread
Author
Thread    Post New Thread    Post A Reply
mattiie
dsy developer

User info:
Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Scusate, sarò un testone ma non ho capito.
Il linguaggio formale che rappresenta la stringa w=aabaa potrebbe essere ad esempio (b*ab*ab*)*
essendo questo rappresentabile da un automa a stati finiti e proprio un linguaggio formale.
Il pumping lemma (a quanto detto dal libro del pighizzini) parla di linguaggi regolari non di grammatiche di tipo 3....

18-04-2011 20:14
Click Here to See the Profile for mattiie Click here to Send mattiie a Private Message Find more posts by mattiie Add mattiie to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

non so se dopo sei a lezione, glielo chiedo cosi vediamo.
probabilmente deve ancora spiegare alcune cose....

19-04-2011 06:48
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
mattiie
dsy developer

User info:
Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

RISOLTO:
Il pumping lemma dice che ESISTE una suddivisione w=xyz che rispetta le tre proprietà ma non tutte.
La suddivisione corretta di aabaa
x=ε
y=aa
z=baa

Non trovo il modo per cambiare il titolo del post.. vorrei aggiungere "[risolto]"

19-04-2011 12:41
Click Here to See the Profile for mattiie Click here to Send mattiie a Private Message Find more posts by mattiie Add mattiie to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

era sfuggita anche a me che esiste una suddivisione, non che siano valide tutte....

19-04-2011 15:12
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
pierprogramm
.novellino.

User info:
Registered: May 2013
Posts: 2 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:18:16 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Scusate ragazzi ma sono disperato. Lo so sto scrivendo in una discussione che risale al 2011, ma cercando online per capire come applicare il PL dei linguaggi regolari, questa discussione mi sembra la migliore specialmente perchè alla fine arrivate alla conclusione che "Il pumping lemma dice che ESISTE una suddivisione w=xyz che rispetta le tre proprietà ma non tutte.".
Io interpreto che BASTA UNA suddivisione di una qualunque stringa affinchè il PL valga, quindi se non c'è neanche una suddivisione che rispetta tutte e tre le proprietà, allora il PL non vale.

Quindi riassumento SE prendendo un qualunque N naturale, ogni suddivisione di UNA SOLA parola di L di lunghezza >=N non rispetta le proprietà (|xy| <= n, |y|>=1 e pompaggio) allora il PL non vale.
Quindi negli esercizi mi basta trovare una parola di L e provare a scomporla in xyz verificando le proprietà, se queste proprietà non valgono (lo sforzo è specialmente sulla proprietà del pompaggio) allora il PL non vale. Giusto?

16-05-2013 16:43
Click Here to See the Profile for pierprogramm Click here to Send pierprogramm a Private Message Visit pierprogramm's homepage! Find more posts by pierprogramm Add pierprogramm to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
aPiso
.illuminato.

User info:
Registered: Sep 2010
Posts: 158 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 21:54:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by pierprogramm
Scusate ragazzi ma sono disperato. Lo so sto scrivendo in una discussione che risale al 2011, ma cercando online per capire come applicare il PL dei linguaggi regolari, questa discussione mi sembra la migliore specialmente perchè alla fine arrivate alla conclusione che "Il pumping lemma dice che ESISTE una suddivisione w=xyz che rispetta le tre proprietà ma non tutte.".
Io interpreto che BASTA UNA suddivisione di una qualunque stringa affinchè il PL valga, quindi se non c'è neanche una suddivisione che rispetta tutte e tre le proprietà, allora il PL non vale.

Quindi riassumento SE prendendo un qualunque N naturale, ogni suddivisione di UNA SOLA parola di L di lunghezza >=N non rispetta le proprietà (|xy| <= n, |y|>=1 e pompaggio) allora il PL non vale.
Quindi negli esercizi mi basta trovare una parola di L e provare a scomporla in xyz verificando le proprietà, se queste proprietà non valgono (lo sforzo è specialmente sulla proprietà del pompaggio) allora il PL non vale. Giusto?


Si' beh devi provare che per ogni possibile divisione per quella parola le condizioni del p.l. non possono mai essere rispettate tutte. A quel punto sei a posto ^^

Edit: qualunque N naturale non saprei, l' N usato dal pumping lemma e' una costante fornita dall' automa che riconosce il linguaggio nel caso il pl sia valido, e corrisponde al numero degli stati.

Last edited by aPiso on 16-05-2013 at 17:04

16-05-2013 16:59
Click Here to See the Profile for aPiso Click Here to See the Blog of aPiso Click here to Send aPiso a Private Message Find more posts by aPiso Add aPiso to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
pierprogramm
.novellino.

User info:
Registered: May 2013
Posts: 2 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:18:16 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Grazie mille! Comincio a capirci qualcosa allora.
Si la storia del numero degli stati la so proviene dalla dimostrazione, infatti si dice per N "abbastanza grande" perchè è >= al numero minimo di stati necessari a costruire l'FSA.

16-05-2013 17:46
Click Here to See the Profile for pierprogramm Click here to Send pierprogramm a Private Message Visit pierprogramm's homepage! Find more posts by pierprogramm Add pierprogramm to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 13:01.    Post New Thread    Post A Reply
Pages (2): « 1 [2]   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.031 seconds (81.92% PHP - 18.08% MySQL) con 25 query.