 |
aPiso |
.illuminato.
Registered: Sep 2010
Posts: 158 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 1 Day, 21:54:30 [...]
Status: Offline
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
|
mattiie
