.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- Help pumping lemma (http://www.dsy.it/forum/showthread.php?threadid=41837)

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....

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

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]"

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

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?

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?

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.