Linguaggi Context-free
Ciao a tutti 
!!!!
Devo dimostrare che il linguaggio $L={0^n 0^(2n^2)|n in NN}$ non è CF. Devo dimostrarlo utilizzando il Pumping Lemma per i linguaggi CF, o per meglio dire la sua negazione.
- Quindi prendo un generico $k in NN$.
- Prendo una stringa $z$ tale che $|z|>=k$, prendo quindi $z=0^k 0^(2k^2)$.
Ora devo dimostrare che per ogni possibile suddivisione della stringa $z$ in cinque sottostringhe $u,v,w,x,y$ tali che $|vwx|<=k$ e $|vx|>=0$, esiste un i tale percui la stringa $uv^iwx^iy !in L$.
Non so se qualcuno di voi ha visto queste cose, comunque sia le stò facendo nel corso di Fondamenti, ma veniamo al problema...
Supponiamo una prima suddivisione della stringa z, ovvero quella in cui $v$ e $x$ stanno nel primo gruppo di zeri.
1) $v,x in 0^k$
Avrò una stringa $z' = 0^(k+|vx|(i-1)) 0^(2k^2)$ Posso fare una dimostrazione di questo tipo? E' valida? (quella che segue)
Scriviamo $z'$ come $z' = 0^a 0^b$ dove $a=k+|vx|(i-1)$ e $b=k^2$, allora $z' in L$ se e solo se $a^2 = b$.
Ma allora avremo che $(k+|vx|(i-1))^2 = k^2$ ovvero $k^2 + |vx|^2(i-1)^2 + 2k|vx|(i-1) = k^2$.
Quest'ultima è vera solamente se $|vx| = 0$ ma ciò non è possibile, perchè mi viola la condizione del Pumping Lemma secondo cui $|vx|>0$...
Poi ci sarebbero gli altri casi, ma per quanto riguarda questo, che dite? Cioè posso ridurmi al problema di $a^2=b$ e procedere come ho fatto?
Grazie...!
!!!!Devo dimostrare che il linguaggio $L={0^n 0^(2n^2)|n in NN}$ non è CF. Devo dimostrarlo utilizzando il Pumping Lemma per i linguaggi CF, o per meglio dire la sua negazione.
- Quindi prendo un generico $k in NN$.
- Prendo una stringa $z$ tale che $|z|>=k$, prendo quindi $z=0^k 0^(2k^2)$.
Ora devo dimostrare che per ogni possibile suddivisione della stringa $z$ in cinque sottostringhe $u,v,w,x,y$ tali che $|vwx|<=k$ e $|vx|>=0$, esiste un i tale percui la stringa $uv^iwx^iy !in L$.
Non so se qualcuno di voi ha visto queste cose, comunque sia le stò facendo nel corso di Fondamenti, ma veniamo al problema...
Supponiamo una prima suddivisione della stringa z, ovvero quella in cui $v$ e $x$ stanno nel primo gruppo di zeri.
1) $v,x in 0^k$
Avrò una stringa $z' = 0^(k+|vx|(i-1)) 0^(2k^2)$ Posso fare una dimostrazione di questo tipo? E' valida? (quella che segue)
Scriviamo $z'$ come $z' = 0^a 0^b$ dove $a=k+|vx|(i-1)$ e $b=k^2$, allora $z' in L$ se e solo se $a^2 = b$.
Ma allora avremo che $(k+|vx|(i-1))^2 = k^2$ ovvero $k^2 + |vx|^2(i-1)^2 + 2k|vx|(i-1) = k^2$.
Quest'ultima è vera solamente se $|vx| = 0$ ma ciò non è possibile, perchè mi viola la condizione del Pumping Lemma secondo cui $|vx|>0$...
Poi ci sarebbero gli altri casi, ma per quanto riguarda questo, che dite? Cioè posso ridurmi al problema di $a^2=b$ e procedere come ho fatto?
Grazie...!
Risposte
Non è corretta, perché non è vero che la stringa $z' = 0^a 0^b$ deve avere $a=k+|vx|(i-1)$ e $b=k^2$ e $a^2 = b$ (e comunque sarebbe stato $2a^2=b$). Ci potrebbe essere un'altra suddivisione di $z'$ in modo da renderla della forma $0^n0^(2n^2)$, senza che $a$ sia per forza della forma in cui la scrivi tu.
Io non procederei per casi, perché non ha importanza dove $vwx$ si colloca.
Io non procederei per casi, perché non ha importanza dove $vwx$ si colloca.
Ciao, intanto grazie per la risposta!
Supponiamo un attimo che io voglia procedere per casi, allora dovrei studiarne tre, ovvero:
- Caso in cui $v,x in 0^k$
- Caso in cui $v,x in 0^(2k^2)$
- Caso in cui $v in 0^k, x in 0^(2k^2)$
I due gruppi di zeri sono legati da una relazione, se io la trovo poi posso utilizzarla per la dimostrazione.
Prendiamo il primo caso, dove $v,x in 0^k$ avrò quindi una stringa $z' = 0^(k + |vx|(i-1)) 0^(2k^2)$ devo quindi dimostrare che esiste una i per cui $z' !in L$.
Come legheresti tu i due gruppi di zeri, per poi procedere con la dimostrazione?
Perchè non posso vedere la stringa $z'$ come $z' = 0^a 0^b$, e procedere come ho fatto tralasciando il 2?
Prendiamo ad esempio il terzo caso dove $v in 0^k, x in 0^(2k^2)$.
Avrò che $z' = 0^(k + |v|(i-1)) 0^(2k^2+|x|(i-1))$
Riscrivo $z'$ in questo modo $z' = 0^(a') 0^(2a^2)$ dove $a' = k + |vx|(i-1)$ e $2a^2 = 2k^2 + |x|(i-1)$.
Se $z' in L$ deve essere che $a'=a$, metto quindi il tutto a sistema...
${(a = k + |vx|(i-1)),(2a^2 = 2k^2 + |x|(i-1)):}$
${(2a^2 = 2k^2 + 2|vx|^2(i-1)^2 + 4k|vx|(i-1)),(2a^2 = 2k^2 + |x|(i-1)):}$
Da cui ottengo $2k^2 + |x|(i-1) = 2k^2 + 2|vx|^2(i-1)^2 + 4k|vx|(i-1)$
Semplificando $|x| = 2|vx|(i-1) + 4k|vx|$
Ora essendo che $|vx| > 0$, per qualsiasi $i>1$ avrò che $|x|>k$, ma questo mi va a violare la condizione del P.L. secondo cui $|vwx|<=k$
Una dimostrazione simile è stata fatta per un altro esercizio, dovrei utilizzare lo stesso procedimento per i primi due casi? Ovvero non posso slegarmi dal termine 2 come ho fatto sopra?
Ripeto, tutto questo se vado ad analizzare caso per caso, ma è una cosa che voglio capire io.
Grazie millle!
Supponiamo un attimo che io voglia procedere per casi, allora dovrei studiarne tre, ovvero:
- Caso in cui $v,x in 0^k$
- Caso in cui $v,x in 0^(2k^2)$
- Caso in cui $v in 0^k, x in 0^(2k^2)$
I due gruppi di zeri sono legati da una relazione, se io la trovo poi posso utilizzarla per la dimostrazione.
Prendiamo il primo caso, dove $v,x in 0^k$ avrò quindi una stringa $z' = 0^(k + |vx|(i-1)) 0^(2k^2)$ devo quindi dimostrare che esiste una i per cui $z' !in L$.
Come legheresti tu i due gruppi di zeri, per poi procedere con la dimostrazione?
Perchè non posso vedere la stringa $z'$ come $z' = 0^a 0^b$, e procedere come ho fatto tralasciando il 2?
Prendiamo ad esempio il terzo caso dove $v in 0^k, x in 0^(2k^2)$.
Avrò che $z' = 0^(k + |v|(i-1)) 0^(2k^2+|x|(i-1))$
Riscrivo $z'$ in questo modo $z' = 0^(a') 0^(2a^2)$ dove $a' = k + |vx|(i-1)$ e $2a^2 = 2k^2 + |x|(i-1)$.
Se $z' in L$ deve essere che $a'=a$, metto quindi il tutto a sistema...
${(a = k + |vx|(i-1)),(2a^2 = 2k^2 + |x|(i-1)):}$
${(2a^2 = 2k^2 + 2|vx|^2(i-1)^2 + 4k|vx|(i-1)),(2a^2 = 2k^2 + |x|(i-1)):}$
Da cui ottengo $2k^2 + |x|(i-1) = 2k^2 + 2|vx|^2(i-1)^2 + 4k|vx|(i-1)$
Semplificando $|x| = 2|vx|(i-1) + 4k|vx|$
Ora essendo che $|vx| > 0$, per qualsiasi $i>1$ avrò che $|x|>k$, ma questo mi va a violare la condizione del P.L. secondo cui $|vwx|<=k$
Una dimostrazione simile è stata fatta per un altro esercizio, dovrei utilizzare lo stesso procedimento per i primi due casi? Ovvero non posso slegarmi dal termine 2 come ho fatto sopra?
Ripeto, tutto questo se vado ad analizzare caso per caso, ma è una cosa che voglio capire io.
Grazie millle!
Non mi torna quello che affermi. Tu sai che la stringa $z' = 0^(k + |v|(i-1)) 0^(2k^2+|x|(i-1))$ per appartenere al linguaggio deve essere della forma $0^a0^(2a^2)$. Ma nessuno ti dice che deve essere $a = k + |vx|(i-1)$ e $2a^2 = 2k^2 + |x|(i-1)$. Questa e' un'ipotesi che fai tu, non corrisponde necessariamente al vero.
No aspetta, non capisco cosa vuoi dire... Ti posto un attimo la dimostrazione fatta per il linguaggio $L2 = {0^(2n) 1 0^(n^2) | n in NN}$
http://img337.imageshack.us/img337/8156/57459834tp7.jpg
Io ho seguito lo stesso procedimento.
PS: Sopra c'è un errore cioè $a = k + |x|(i-1)$ non $|vx|$.
http://img337.imageshack.us/img337/8156/57459834tp7.jpg
Io ho seguito lo stesso procedimento.
PS: Sopra c'è un errore cioè $a = k + |x|(i-1)$ non $|vx|$.
"enigmagame":
Ti posto un attimo la dimostrazione fatta per il linguaggio $L2 = {0^(2n) 1 0^(n^2) | n in NN}$
http://img337.imageshack.us/img337/8156/57459834tp7.jpg
.
Dove ho già visto questo esercizio? ehm... a verona!
Il metodo di risoluzione del nostro esercizio deve essere diverso dal metodo di risoluzione per il linguaggio $0^(2k)10^(k^2)$ perché in quest'ultimo caso i gruppi sono determinati dalla presenza dell'1 separatore. La risolutrice dell'esercizio pone $2h=2k+|v|(i-1)$ poiche' sa che la stringa di zeri contenente $v$ e' a sinistra dell'1, e analogamente pone $h^2=k^2+|x|(i-1)$ poiche' sa che la stringa di zeri contenente $x$ e' a destra dell'1.
Nel nostro caso, non abbiamo qualcosa di analogo ad un separatore centrale, e quindi
"fields":
Non mi torna quello che affermi. Tu sai che la stringa $z' = 0^(k + |v|(i-1)) 0^(2k^2+|x|(i-1))$ per appartenere al linguaggio deve essere della forma $0^a0^(2a^2)$. Ma nessuno ti dice che deve essere $a = k + |v|(i-1)$ e $2a^2 = 2k^2 + |x|(i-1)$. Questa e' un'ipotesi che fai tu, non corrisponde necessariamente al vero.
Tu hai applicato un metodo che andava bene per un altro esercizio, non per il nostro. Nel nostro caso la stringa è di solo zeri, e quindi non sai dove inizia e finisce la parte $a$ e dove inizia e finisce la parte $2a^2$.
"fields":
Dove ho già visto questo esercizio? ehm... a verona!
Hehehehe ricordi?
Comunque si, hai perfettamente ragione, c'è di mezzo quell'uno che noi non abbiamo, ed ecco il perchè nel primo esercizio è inutile studiare tutti i casi, perchè non hai importanza la collocazione della stringa $|vwx|$.
Però ti chiedo un altra cosa, la dimostrazione sbagliata del primo esercizio, quella in cui suppongo che $|vx|$ appartengano allo stesso gruppo di zeri, non posso usarla correttamente in questo secondo? Nel testo dell'immagine la questione viene liquidata dicendo che viene a saltare la relazione che esiste tra i due grupp di zeri, ma formalmente non viene dimostrato nulla, si potrebbe fare come ho detto io no?
Grazie mille!
"enigmagame":
Però ti chiedo un altra cosa, la dimostrazione sbagliata del primo esercizio, quella in cui suppongo che $|vx|$ appartengano allo stesso gruppo di zeri, non posso usarla correttamente in questo secondo? Nel testo dell'immagine la questione viene liquidata dicendo che viene a saltare la relazione che esiste tra i due grupp di zeri, ma formalmente non viene dimostrato nulla, si potrebbe fare come ho detto io no?
Sì, il tuo metodo si applica correttamente al secondo esercizio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo