vfldj

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:

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.

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

Wo aspetta, prima di tutto il pumping lemma NON è un teorema, semplicemente esprime la condizione NECESSARIA ma NON SUFFICIENTE affinchè un linguaggio sia regolare o context-free: quindi se la condizione è soddisfatta allora è ancora tutto da vedere, altrimenti non si tratterà di un linguaggio context-free o regolare a seconda dei casi (e fino a qui ho ripetuto quello che tu hai detto).
Ora giungo al problema che poni tu: come faccio a dimostrare che un linguaggio è regolare (o context free?)? la risposta è molto semplice: devi riuscire a esprimere tale linguaggio con un automa a stati finiti o con una espressione regolare, (per un linguaggio CF sarà un automa a pila o una grammatica).

Riguardo l'esercizio non capisco il descrittore:
L={abncmbn|n,m>0}, l'alfabeto cui si riferisce è (a,b,c,m,n)? oppure intendi L={ab^n c^m b^n | n,m>0}?

vfldj

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:

Originally posted by Cronovirus
Wo aspetta, prima di tutto il pumping lemma NON è un teorema, semplicemente esprime la condizione NECESSARIA ma NON SUFFICIENTE affinchè un linguaggio sia regolare o context-free: quindi se la condizione è soddisfatta allora è ancora tutto da vedere, altrimenti non si tratterà di un linguaggio context-free o regolare a seconda dei casi (e fino a qui ho ripetuto quello che tu hai detto).
Ora giungo al problema che poni tu: come faccio a dimostrare che un linguaggio è regolare (o context free?)? la risposta è molto semplice: devi riuscire a esprimere tale linguaggio con un automa a stati finiti o con una espressione regolare, (per un linguaggio CF sarà un automa a pila o una grammatica).

Riguardo l'esercizio non capisco il descrittore:
L={abncmbn|n,m>0}, l'alfabeto cui si riferisce è (a,b,c,m,n)? oppure intendi L={ab^n c^m b^n | n,m>0}?

Si scusa intendevo L={ab^n c^m b^n | n,m>0}

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

ok, prima di tutto non è regolare perchè se provi ad applicare il pumping lemma su una stringa w = xyz in cui:
1) y!=epsilon
2) |xy| <= n
3) xy^kz per ogni k appartiene ancora a L

prendiamo una costante n, beh si nota che siccome |xy|<n allora la stringa xy non conterrà 'c' ma solo una 'a' e delle 'b', bene ma adesso se replichi y quante volte vuoi dato che contiene almeno una 'b', avrà sicuramente più 'b' che nella stringa 'z', quindi il linguaggio non è regolare.

Se provi a applicare il pumping lemma per i CF non ne esci (o almeno io non ci sono riuscito), quindi intuitivamente provo a spiegarti un automa a pila che accetta tale linguaggio (sperando sia giusto).

il primo simbolo da leggere è una 'a', quindi ci sarà una transizione su tale simbolo in uno stato, dunque inizia a leggere tutte le 'b' (un numero qualsiasi); leggi anche le 'c' ma non inserire nulla sulla pila, semplicemente rimani nello stato corrente, dunque quando ritorni a leggere le 'b' inizia a toglierle dalla cima della pila. Se alla fine dell'input la pila è vuota, allora accetta!

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

anzi! quando leggi una c devi andare in un nuovo stato, dal quale fino a quando leggi 'c' ci rimani, quando leggi una 'b' vai in un nuovo stato inizi a svuotare la pila!!

vfldj

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:

Originally posted by Cronovirus

prendiamo una costante n, beh si nota che siccome |xy|<n allora la stringa xy non conterrà 'c' ma solo una 'a' e delle 'b', bene ma adesso se replichi y quante volte vuoi dato che contiene almeno una 'b', avrà sicuramente più 'b' che nella stringa 'z', quindi il linguaggio non è regolare.

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

prendi una stringa generica w = xyz dal tuo linguaggio
L={ab^n c^m b^n | n,m>0} e una costante (chiamiamola k) DIPENDENTE dal linguaggio, che in questo caso sarà chiaramente k = n.

ora:
1) la parte centrale, y, della tua stringa deve essere diversa dalla stringa vuota
2) |xy| <= k

proprio per il punto 2 xy sarà una stringa che contiene solo una 'a' e k - 1 'b'
(se prendiamo k = n = 3 per esempio e quindi una stringa abbbcbbb, la stringa xy può essere 'abb', dove y = b per esempio)

manca il punto da soddisfare:
3) per ogni j > 0 xy^j z è in L

ma tu vedi bene che se replichi y quante volte vuoi, (per esempio 3 , 4 etc volte..) la tua stringa non appartiene più al linguaggio perchè avrai più b nella prima parte che nella seconda, mentre tu vuoi che siano dello stesso numero!

in pratica:

per un k, ad esempio 3, con la stringa abbbcbbb:

xy = abb e y = b (dato che non può essere nulla)

per j = 3 xy^jz = ab bbb cbbb

se fosse stato un linguaggio regolare avresti avuto tante 'b' a sinistra di 'c', quante a destra.

Se non ti è chiaro il perchè il pumping lemma funziona ti consiglio di gurdarne la dimostrazione intuitiva!

vfldj

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:

Originally posted by Cronovirus
prendi una stringa generica w = xyz dal tuo linguaggio
L={ab^n c^m b^n | n,m>0} e una costante (chiamiamola k) DIPENDENTE dal linguaggio, che in questo caso sarà chiaramente k = n.

ora:
1) la parte centrale, y, della tua stringa deve essere diversa dalla stringa vuota
2) |xy| <= k

proprio per il punto 2 xy sarà una stringa che contiene solo una 'a' e k - 1 'b'
(se prendiamo k = n = 3 per esempio e quindi una stringa abbbcbbb, la stringa xy può essere 'abb', dove y = b per esempio)

manca il punto da soddisfare:
3) per ogni j > 0 xy^j z è in L

ma tu vedi bene che se replichi y quante volte vuoi, (per esempio 3 , 4 etc volte..) la tua stringa non appartiene più al linguaggio perchè avrai più b nella prima parte che nella seconda, mentre tu vuoi che siano dello stesso numero!

in pratica:

per un k, ad esempio 3, con la stringa abbbcbbb:

xy = abb e y = b (dato che non può essere nulla)

per j = 3 xy^jz = ab bbb cbbb

se fosse stato un linguaggio regolare avresti avuto tante 'b' a sinistra di 'c', quante a destra.

Se non ti è chiaro il perchè il pumping lemma funziona ti consiglio di gurdarne la dimostrazione intuitiva!

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

1) di 'a' a inizio stringa ne devi avere una sola
2) il pumping lemma parla esplicitamente di una certa costante dipendente dal linguaggio, quindi è un passaggio necessario al lemma per la sua correttezza, non puoi scegliere una costante a caso diversa da quella del linguaggio così da riuscire ad inglobare anche le 'c' per esempio.

Se ti può convincere di più: siccome un linguaggio è regolare se si riesce ad esprimerlo tramite un automa a stati finiti, questa costante del pumping lemma si riferisce proprio al numero di stati dell'ideale automa nel senso che:
se hai n stati e una stringa di lunghezzastrettamente maggiore di n, affinchè tale stringa sia accettata ci deve esserci per forza un loop (ciclo, transizione su se stesso chiamalo come vuoi) su uno stato, quindi nulla vieta di poter ciclare all'infinito su tale stato.

vfldj

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:

Originally posted by Cronovirus
1) di 'a' a inizio stringa ne devi avere una sola
2) il pumping lemma parla esplicitamente di una certa costante dipendente dal linguaggio, quindi è un passaggio necessario al lemma per la sua correttezza, non puoi scegliere una costante a caso diversa da quella del linguaggio così da riuscire ad inglobare anche le 'c' per esempio.

Se ti può convincere di più: siccome un linguaggio è regolare se si riesce ad esprimerlo tramite un automa a stati finiti, questa costante del pumping lemma si riferisce proprio al numero di stati dell'ideale automa nel senso che:
se hai n stati e una stringa di lunghezzastrettamente maggiore di n, affinchè tale stringa sia accettata ci deve esserci per forza un loop (ciclo, transizione su se stesso chiamalo come vuoi) su uno stato, quindi nulla vieta di poter ciclare all'infinito su tale stato.