Lun 18 Marzo, 18:28:50 - 2019

Autore Topic: Problemi nell'applicazione del pumping lemma  (Letto 609 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Problemi nell'applicazione del pumping lemma
« il: Gio 30 Marzo, 17:35:48 - 2017 »
Ho dei problemi nell'applicazione del pumping lemma per dimostrare se un linguaggio L è non regolare. Qualcuno può aiutarmi? In partcolare come applicarlo ad esempio per L1 = {akbak k>0} e L2= {ah, bk, h>0, k >0 } che sono non regolari.

La definizione del pumping lemmma è questa:
Se L é regolare, allora esiste n>0 tale che per ogni z appartenente ad L, |z| > n, esistono stringhe u, v, w tale che:
1. z = uvw
2. |uv|< n
3  |v| > 1
4. zi = uviw appartiene ad L, per ogni i= 0,1,2,.... numeri naturali
 
« Ultima modifica: Gio 30 Marzo, 17:47:32 - 2017 da scheggia89 »

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #1 il: Ven 31 Marzo, 11:41:42 - 2017 »
Spero di non scrivere scemenze, mi scuso in anticipo ma ci provo :asd:
Allora il pumping lemma serve a capire che un linguaggio non è del tipo in questione, quindi di tipo regolare, quindi almeno di tipo 2.

1) Il primo linguaggio, partiamo per assurdo, che il linguaggio L1 sia regolare:
Quindi scegliamo n* = 1

perciò mettendo k=n troviamo che "n+1+n>n*, 2n+1>n" quindi la condizione che |z|>=n si verifica.

Allora riscriviamo per n = 1: "aba"
per il pumping lemma questa deve essere suddivissa in 3 sottostringhe quindi:

a = u
b= v
a = w

Allora la seconda condizione dice che |uv| <= n quindi |UV|<=1, cosa che no può verificarsi dato che |uv| è 2.
Se la seconda condizione dovesse verificarsi allora "b" dovrebbe essere nulla, ma questa va contro la condizione 3 e 4 che dicono che "b" non deve essere nulla. In conclusione Il ilnguaggio non può essere regolare.

2) Il secondo linguaggio, scegliamo n* = 1 allora h e k = 1, quindi |z| = 2. Troviamo che la condizione |z|>=n* si verifica (2>1)

Riscriviamo ora la stringa per h e k = 1:

"ab"

Questa dovrebbe poter essere suddivissa in 3 sottostringhe, cosa impossibile.
Possiamo pensare che "v" è nulla, ma questo viola la 3 e 4 condizione che dicono che "v" non può essere nulla. In conclusione il linguaggio non può essere regolare.

Io avrei fatto così, ma come sempre non sono sicuro  :-X :-X :-X

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #2 il: Ven 31 Marzo, 12:59:01 - 2017 »
Spero di non scrivere scemenze, mi scuso in anticipo ma ci provo :asd:
Allora il pumping lemma serve a capire che un linguaggio non è del tipo in questione, quindi di tipo regolare, quindi almeno di tipo 2.

1) Il primo linguaggio, partiamo per assurdo, che il linguaggio L1 sia regolare:
Quindi scegliamo n* = 1

perciò mettendo k=n troviamo che "n+1+n>n*, 2n+1>n" quindi la condizione che |z|>=n si verifica.

Allora riscriviamo per n = 1: "aba"
per il pumping lemma questa deve essere suddivissa in 3 sottostringhe quindi:

a = u
b= v
a = w

Allora la seconda condizione dice che |uv| <= n quindi |UV|<=1, cosa che no può verificarsi dato che |uv| è 2.
Se la seconda condizione dovesse verificarsi allora "b" dovrebbe essere nulla, ma questa va contro la condizione 3 e 4 che dicono che "b" non deve essere nulla. In conclusione Il ilnguaggio non può essere regolare.

2) Il secondo linguaggio, scegliamo n* = 1 allora h e k = 1, quindi |z| = 2. Troviamo che la condizione |z|>=n* si verifica (2>1)

Riscriviamo ora la stringa per h e k = 1:

"ab"

Questa dovrebbe poter essere suddivissa in 3 sottostringhe, cosa impossibile.
Possiamo pensare che "v" è nulla, ma questo viola la 3 e 4 condizione che dicono che "v" non può essere nulla. In conclusione il linguaggio non può essere regolare.

Io avrei fatto così, ma come sempre non sono sicuro  :-X :-X :-X

Nel primo linguaggio perché scegli n* =1 e quindi metti k = n? Sicuramente Sarò idiota io ahahaah ma non riesco a capire il nesso logico. Per il resto il ragionamento fila, quindi penso vada bene. Lo stesso dubbio lo ho nel linguaggio quando scegli n* = 1 e quindi h, k = 1.

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #3 il: Ven 31 Marzo, 13:45:06 - 2017 »
Ripeto, mi scuso per le eventuali scemenze che forse andrò a scrivere  :-X :-X :-X :asd: :asd: :asd:

Guarda, ho cercato su internet ma non ho trovato una risposta precisa e convincente sul perchè  :-\ :-\ :-\  Poi sulle slide la parte del pumping non si capisce molto bene :-\

Prendi con le pinze ciò che sto per scrivere !! :sisi: :sisi: :sisi:
Ma ho ragionato così:

Allora, "n" è una variabile dipendente dal linguaggio che corrisponde alla lunghezza minima che può assumere un carattere della stringa. Cioè corrisponde al numero di transizioni da uno stato all'altro in un automa che riconosce quel linguaggio, quindi se ho un linguaggio a3b3c3 ho bisogno di almeno 3 transizioni, quindi se sommiamo tutte le transizioni di tutto il linguaggio abbiamo che |z|>=n cioè 9>3

In tutti gli esercizi sui pumping ho ragionato così, sia per quelli di tipo context free e regolare

Magari se qualcuno ce lo può spiegare meglio sarebbe ottimo, ma misa siamo gli unici sopravvissuti  :'( :asd:

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #4 il: Ven 31 Marzo, 15:21:15 - 2017 »
Ripeto, mi scuso per le eventuali scemenze che forse andrò a scrivere  :-X :-X :-X :asd: :asd: :asd:

Guarda, ho cercato su internet ma non ho trovato una risposta precisa e convincente sul perchè  :-\ :-\ :-\  Poi sulle slide la parte del pumping non si capisce molto bene :-\

Prendi con le pinze ciò che sto per scrivere !! :sisi: :sisi: :sisi:
Ma ho ragionato così:

Allora, "n" è una variabile dipendente dal linguaggio che corrisponde alla lunghezza minima che può assumere un carattere della stringa. Cioè corrisponde al numero di transizioni da uno stato all'altro in un automa che riconosce quel linguaggio, quindi se ho un linguaggio a3b3c3 ho bisogno di almeno 3 transizioni, quindi se sommiamo tutte le transizioni di tutto il linguaggio abbiamo che |z|>=n cioè 9>3

In tutti gli esercizi sui pumping ho ragionato così, sia per quelli di tipo context free e regolare

Magari se qualcuno ce lo può spiegare meglio sarebbe ottimo, ma misa siamo gli unici sopravvissuti  :'( :asd:
Purtroppo me sa de si, siamo gli unici sopravissuti :( Cmq ho capito il ruolo di n ma nel caso specifico non capisco il fatto quando dici: scelgo n* = 1 e poi metti k=n? questo non riesco a capire :(

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #5 il: Ven 31 Marzo, 16:52:27 - 2017 »
Allora, "n" è il numero tale che per ogni stringa appartenente al linguaggio di almeno "n" possa esistere una scomposizione "w=xyz" e si possano verificare (in teoria) le varie regole del pumping (ragiono per assurdo).
Quindi mettendo "k" = "n" scelgo il numero più piccolo permesso affinché "in teoria" possa venire fuori una stringa che mi permetta la scomposizione in w=xyz nel caso del pumping lemma dei linguaggi regolare.

Da un occhiata all'esempio del pumping lemma per i context free su wikipedia, hanno fatto una cosa simile a quello che ho fatto io:   ::) :P

https://it.wikipedia.org/wiki/Pumping_lemma_per_i_linguaggi_liberi_dal_contesto

Se sei riuscito a capire qualcosa in più scrivilo che sicuramente servirà anche a me  ;D ;D ;D ;D
« Ultima modifica: Ven 31 Marzo, 23:06:42 - 2017 da john »

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #6 il: Ven 31 Marzo, 18:20:25 - 2017 »
Credo di aver capito il tuo ragionamento :D E secondo me é sensato quello che hai detto :D

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Problemi nell'applicazione del pumping lemma
« Risposta #7 il: Mer 19 Luglio, 17:36:58 - 2017 »
Sto provando a risolvere il seguente esercizio:
Sia L={ ahbkch+k : h, k >0 . Dimostare che L non è regolare.

Il mio ragionamento è questo:

Per assurdo L è regolare. Affinchè |z|> n, scelgo n=4. Quindi per n=4  , z=abcc.
1) z=uvw , è verificata suddividendo z in: u=a v=bc w=c.
2) |uv| < n, è verificata, infatti |uv| = 3 < 4 = n.
3) |v| > 1, è  verificata, infatti |v|=2 > 1
4) non viene mai verificata perchè "pompando" v, z non appartiene al linguaggio L. Infatti:
    i=0    z= ac
    i=1    z=abcbcc
    i=2    z=abcbcbcc.

Quindi L non è regolare. Che ne pensate del mio ragionamento?Ho sbagliato qualcosa? Si accettano suggerimenti che non sono sicuro di ciò.

Inoltre ho provato anche a dimostrare se L={ ss | s c {a,b}* } non è regolare, ma non riesco a scegliere n  e quindi non so come risolverlo.
« Ultima modifica: Mer 19 Luglio, 17:53:06 - 2017 da scheggia89 »