Pages: [1]   Go Down
Print
Author Topic: Dubbio pumping lemma  (Read 1017 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Carmelo-Musumarra
Matricola
*
Offline Offline

Posts: 23


« on: 22-11-2014, 10:13:59 »

Salve a tutti,
Mi è sorto un dubbio circa il pumping lemma...
Esso dice che esiste una costante n = |Q| e una z appartenente ad un linguaggio dove se |z| >= n allora possiamo scriverla come uvw. Con |uv|<=n, |v| >=1. Ottenendo che uviw appartiene al linguaggio per ogni i>=0.
Ma se i dovesse valere appunto 0, vi sarebbe uguale alla stringa vuota no? Ciò non entra in contrasto con |v|>=1?
« Last Edit: 22-11-2014, 10:56:57 by Carmelo-Musumarra » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Online Online

Gender: Male
Posts: 4.466


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #1 on: 22-11-2014, 11:01:29 »

Come al solito, se non studi la dimostrazione del teorema, tutto il suo enunciato sarà un enigma per chi lo ascolta.

Il pumping lemma afferma la seguente cosa:

Hai un linguaggio (che sai già essere) regolare?
Bene, allora (e solo in quel caso), considerato il numero di stati n di un automa qualsiasi che la accetta, per ogni parola x sufficientemente lunga, diciamo con almeno n simboli (e non è detto che ce ne siano in un tale linguaggio sebbene sia regolare!), posso esibire una sua decomposizione in uvw, con |uv|≤n e |v|>0, tale che, per ogni i naturale, la parola uviw è ancora nel linguaggio.

Scendo ancora un po' nel dettaglio fornendo cenni della dimostrazione.
Hai un linguaggio (che sai già essere) regolare?
Bene. Considera un automa qualsiasi che lo accetta/denota.
Ora, considera il diagramma di transizione di tale automa: se tale diagramma ha almeno un ciclo al suo interno (proprio così, se non ci sono cicli il resto del discorso non viene applicato), e tale ciclo viene attraversato almeno una volta per poi passare almeno una volta da almeno uno stato finale, allora significa che posso attraversare quante volte voglio quel ciclo (anche zero, di fatto non attraversandolo mai, rimanendo nel suo nodo di inizio=di fine ciclo) ottenendo ancora parole del linguaggio.

La questione del ciclo attraversato almeno una volta passando poi almeno una volta da almeno uno stato finale viene elegantemente sintetizzata nella espressione "x lunga almeno quanto n": infatti, se tu hai n stati, e la tua stringa contiene almeno n simboli, per il principio della piccionaia devi aver attraversato un certo stato almeno 2 volte, e l'attraversamento di uno stato più di una volta, nel caso di cammini su grafi, in informatica è detto "ciclo", dunque siamo in presenza di un ciclo.

Il ciclo considerato (cioè le lettere degli archi, in sequenza, attraversati da quando esci per la prima volta dallo stato di inizio=di fine ciclo, fino all'ultimo attraversato prima di ri-entrare nello stato di inizio=di fine ciclo una k-esima volta, k scelto a piacere) sarebbe proprio la sotto-stringa v, che, in quanto ciclo, può essere concatenata quante volte vuoi (attraversare il ciclo quante volte vuoi), anche zero volte (non attraversando il ciclo, di fatto), ottenendo che poi puoi riprendere il percorso che avresti preso prima, dopo aver lasciato il ciclo, cioè w, per terminare su uno stato finale. u sarebbe ciò che leggi prima di entrare per la prima volta nello stato di inizio=di fine ciclo.

Ho preferito scrivere tutta questa pappardella, perché per spiegarti come mai la tua domanda era mal posta ci sarebbe voluto di più, e probabilmente non ci saremmo comunque capiti testate...
« Last Edit: 23-11-2014, 05:26:58 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.927



WWW
« Reply #2 on: 22-11-2014, 11:27:14 »

Come al solito, se non studi la dimostrazione del teorema, tutto il suo enunciato sarà un enigma per chi lo ascolta.


Caro Reverse, il problema e' che  non si studia NEANCHE l'enunciato!!

Carmelo cita infatti l'enunciato dicendo
esiste una costante n = |Q| e una z appartenente ad un linguaggio dove se |z| >= n allora...

il fatto e' che l'enunciato dice che
esiste una costante n tale che, se prendi una stringa z con |z| >= n allora...
L'affermazione di Carmelo e' del tipo Esiste n ed Esiste z  con |z| >= n
mentre l'enunciato afferma Esiste n tale che Per ogni z  con |z| >= n

Inoltre, quale sarebbe la contraddizione tra
|v|>1 ed il fatto che v0 sia la stringa vuota?
Sarebbe come vedere una contraddizione nel fatto che 9>5 e che
daricequadrata(9)<5.

E' ovvio che si incontrino all'inizio delle difficolta' con il linguaggio formale,
ma e' proprio per questo che ci sono anche i corsi di Analisi e Matematica Discreta.
La domanda che vorrei porre a Carmelo e':
Stai seguendo qualcuno di questi corsi?

Detto questo, complimenti a Carmelo per l'impegno, e un ringraziamento
a Reverse per il valido aiuto che gli ha dato.

Un caro saluto
FB
« Last Edit: 22-11-2014, 11:32:02 by Franco Barbanera » Logged
Carmelo-Musumarra
Matricola
*
Offline Offline

Posts: 23


« Reply #3 on: 22-11-2014, 12:19:19 »

Ringrazio intanto sia Reverse che lei Professore, per gli interventi tempestivi...
Rispondendo a lei Professore... Non seguo nessuno dei due corsi (anche se mi piacerebbe dato che a me la matematica piace), non per mancanza di tempo... Ma perchè non li riesco a seguire in quanto essendo entrato con debito formativo (anche se superato), non si può recuperare 5 anni di superiori con 5 giorni di corso zero. Non é un corso zero ma un corso 100 mila.
Di conseguenza un corso zero del genere comporta non riuscire a capire gli argomenti di queste due materie.
Dico un'ultima cosa perchè sono andato già off-topic, anzi scusate... Ma negli anni a venire sarebbe buono che il dipartimento strutturi un corzo zero che duri un anno... Io da studente (partendo con debito) sarei disposto a farmi 4 anni di corso anziché 7, per recuperare da autodidatta la matematica, o spendere soldi in Professori privati oltre a quelli per la tassa universitaria e libri.
Mi scuso ancora e soprattutto con lei Professore, la mia risposta non è assolutamente mirata a offendere lei o il dipartimento.
Spero che con gli anni il corso zero venga rivisto...
Un saluto a tutti e un buon proseguimento.
Logged
Carmelo-Musumarra
Matricola
*
Offline Offline

Posts: 23


« Reply #4 on: 22-11-2014, 19:24:16 »

Ho letto più di una volta il commento di reverse e mi è chiaro tranne sempre per l'unica cosa che mi ha spinto a creare il topic.
Perchè se la cardinalità di v deve essere almeno 1, è ammesso vi con i =0 che sarebbe la stringa vuota che ha cardinalità zero?
Purtroppo ho il difetto (o pregio) di non passare avanti con gli argomenti se una cosa non mi quadra. E come stamattina, questa è l'unica cosa che mi impedisce di farlo.
Come fa v ad essere uguale almeno ad 1 se dovesse verificarsi il caso con i=0? E quindi non attraversando mai gli stati di v che comportano il ciclo di v, assegnando quindi alla sottostringa v almeno un carattere?
« Last Edit: 22-11-2014, 20:49:20 by Carmelo-Musumarra » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Online Online

Gender: Male
Posts: 4.466


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #5 on: 22-11-2014, 21:42:20 »

Ho letto più di una volta il commento di reverse e mi è chiaro tranne sempre per l'unica cosa che mi ha spinto a creare il topic.
Perchè se la cardinalità di v deve essere almeno 1, è ammesso vi con i =0 che sarebbe la stringa vuota che ha cardinalità zero?
Purtroppo ho il difetto (o pregio) di non passare avanti con gli argomenti se una cosa non mi quadra. E come stamattina, questa è l'unica cosa che mi impedisce di farlo.
Come fa v ad essere uguale almeno ad 1 se dovesse verificarsi il caso con i=0? E quindi non attraversando mai gli stati di v che comportano il ciclo di v, assegnando quindi alla sottostringa v almeno un carattere?
A costo di sembrare ripetitivo, farò la parafrasi della parte su cui hai dubbi, confrontandola con la dimostrazione del teorema...

Sia L regolare.Sia L regolare. Dunque esiste un automa che lo accetta.
Sia n il numero di stati di un automa che accetta L.Sia n il numero di stati di tale automa.
Allora,Allora,
per ogni parola x di L, con |x|≥nconsidero una parola del linguaggio che ha abbastanza simboli, almeno n.
Per essere così lunga, significa che, nel diagramma di transizione, leggendone i simboli a partire dallo stato iniziale, a un certo punto attraverserò uno stesso nodo due volte, creando di fatto un ciclo. Senza perdita di generalità, fra tutti i possibili cicli, scegliamo quello che ha meno nodi, cioè in cui si ha al più un nodo che si ripeta, e si ripeta al più 2 volte: un ciclo è uno speciale cammino in un grafo, e la sua etichetta (del cammino/ciclo), che è una stringa, chiamiamola v, per brevità.
esiste una decomposizione di x in uvw, oveCiò che viene prima del ciclo (preciclo) lo chiamiamo u, e ciò che viene dopo (postciclo), lo chiamiamo w (sia u sia w, che sono stringhe, possono essere anche stringhe vuote, senza problemi): in questo modo, la parola x può essere scritta come preciclo⋅ciclo⋅postciclo, cioè u⋅v⋅w.
|v|>0L'etichetta del ciclo, in quanto il ciclo esiste, ha almeno un simbolo, cioè |v|>0.
e
|uv|≤nRiguardo alla lettura parziale fino al ciclo, ciclo inclusa (cioè la lettura di uv), considero che ci sarà esattamente un arco (stringa di lunghezza 1) che unisce uno dei nodi, visitati per adesso una sola volta, al nodo visitato esattamente due volte (la cui seconda visita avviene proprio ora!): poiché i nodi visitati ancora una volta sola sono al più n (una visita per ciascun nodo dell'automa, al massimo), la stringa letta sarà lunga la più n-1 simboli (per n stati passa una stringa di n-1 simboli, visto che l'attraversamento del primo, che è l'iniziale, non comporta lettura simboli, quindi uno in meno del numero di stati) e unendo un altro arco che collega l'ultimo di questi nodi visitati una sola volta al nodo che sarà visitato adesso per la sua seconda volta, ottengo di aggiungere/leggere un solo altro simbolo, ottenendo una stringa uv di lunghezza al più pari a (n-1)+1=n.
tale cheA questo punto
per ogni i∈N, si haper ogni numero i di volte per cui voglio attraversare in sequenza immediata il ciclo (0 volte, 1 volta, 2 volte, ...)
uviw∈Lsi ha che le stringhe ottenute leggendo, nell'ordine, prima il preciclo, poi i volte in sequenza immediata il ciclo, infine postciclo (cioè uviw, per ogni i naturale) mi portano allo stesso stato in cui sarei finito leggendo uvw=x, che essendo quest'ultima una stringa del linguaggio, è uno stato finale, quindi mi portano in definitiva a uno stato finale, detto altrimenti questo tipo di stringhe sono tutte nel linguaggio.
univ pray testate pc

Suggerimento: fai finta di non aver mai sentito parlare di pumping lemma prima d'ora e studia da capo questa versione della dimostrazione. Sono convinto, infatti, che il tuo blocco dipenda dal fatto che nella tua testa ci siano due versioni diverse dello stesso concetto, una mal compresa, e una chiara, che ovviamente non si incrociano in almeno un punto (quello su cui tu ti confondi). Dimenticando la versione mal compresa, apprenderai solo la versione chiara (questa!).
« Last Edit: 23-11-2014, 23:14:52 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Carmelo-Musumarra
Matricola
*
Offline Offline

Posts: 23


« Reply #6 on: 23-11-2014, 10:17:55 »

Addirittura con la parafrasi    ...
Comunque ti ringrazio sia per l'aiuto che per la pazienza che ci hai messo...
Vedrò di farmelo entrare bene in testa 
Una buona domenica...
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.927



WWW
« Reply #7 on: 23-11-2014, 10:49:30 »

Ringrazio intanto sia Reverse che lei Professore, per gli interventi tempestivi...
Rispondendo a lei Professore... Non seguo nessuno dei due corsi (anche se mi piacerebbe dato che a me la matematica piace), non per mancanza di tempo... Ma perchè non li riesco a seguire in quanto essendo entrato con debito formativo (anche se superato), non si può recuperare 5 anni di superiori con 5 giorni di corso zero. Non é un corso zero ma un corso 100 mila.

La soluzione pero' non e' quella di non soguire i corsi di matematica, ma
al contrario, concentrarsi su di essi.
Se il tuo problema e' la matematica, e' li' che devi dedicare maggiormente la tua attenzione.
Ripeto il mio suggerimento: se non ce la fai a seguire tutti i corsi ed hai i problemi che dici,
segui solo i corsi di Matematica!!


Mi scuso ancora e soprattutto con lei Professore, la mia risposta non è assolutamente mirata a offendere lei o il dipartimento.
Spero che con gli anni il corso zero venga rivisto...

E quale offesa sarebbe fornire uno spunto di riflessione?

Un caro saluto
FB
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.927



WWW
« Reply #8 on: 23-11-2014, 10:51:31 »

Apro formalmente una petizione tra le matricole per far erigere una statua equestre a Reverse!

FB
Logged
Carmelo-Musumarra
Matricola
*
Offline Offline

Posts: 23


« Reply #9 on: 23-11-2014, 11:20:35 »

Quote
|v|>0   L'etichetta del ciclo, in quanto il ciclo esiste, ha almeno un simbolo, cioè |v|>0.

Cioè la dimostrazione del libro con |v|>0 intende la cardinalità del ciclo, e non della stringa che (a questo punto non attraversando mai un arco del ciclo se i=0, ma attraversando direttamente archi della stringa w), può anche essere una stringa vuota?

Quote
La solzione pero' non e' quella di non soguire i corsi di matematica, ma
al contrario, concentrarsi su di essi.

Era per non rimanere fermo con le materie, e darne almeno una.
Il suo suggerimento è più che considerato: e nel caso in cui nelle varie materie (di cui farò esami) dovessi prendere meno di un tot da me prefissato, dovrò per forza seguirlo  .

Quote
Apro formalmente una petizione tra le matricole per far erigere una statua equestre a Reverse!

  e siamo a 1 
Certo anche se con il discorso della parafrasi mi sono sentito un po' triste...      
Logged
Pages: [1]   Go Up
Print
Jump to: