Forum Informatica Unict » LAUREA TRIENNALE (D.M. 270/04) » I anno » Fondamenti di Informatica, 9 CFU (Moderators: Giuseppe Scollo, Marina Madonia, Franco Barbanera) » pumping lemma
Pages: [1]   Go Down
« precedente successivo »
Print
Author Topic: pumping lemma  (Read 468 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gerasia
Matricola
*
Offline Offline

Posts: 31
« on: 10-01-2018, 18:10:09 »
ho provato a fare questo esercizio sul pumping lemma, qualcuno potrebbe dirmi se è corretto o meno??
L={an bn |n>=0}
pongo come ipotesi:
n=3      x=aabb
adesso verifico le proprietà( boh) del pumping lemma:
|uv|=|aa|<3
|v|=1
Xi0=uv0z
Xi0=abb che non appartiene al linguaggio,
 quindi posso affermare che il linguaggio L={an bn |n>=0} non è un linguaggio regolare
Logged
teo998
Matricola
*
Offline Offline

Posts: 43



WWW
« Reply #1 on: 11-01-2018, 18:19:08 »
non credo si possa porre n a piacere, perché il suo valore dipende dall'automa che riconosce il linguaggio
puoi porre x a piacere, chiaramente in funzione della variabile n

l'esercizio comunque è svolto nell'ausiello
Logged
Gerasia
Matricola
*
Offline Offline

Posts: 31
« Reply #2 on: 11-01-2018, 19:54:09 »
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Logged
ScavoRosario98
Matricola
*
Offline Offline

Posts: 5
« Reply #3 on: 11-01-2018, 20:45:17 »
Provo a risolverlo ma non garantisco la correttezza dello svolgimento.
Dato il linguaggio L={a^n b^n |n>=0}
Deduco che il 'numero di a' deve essere uguale al 'numero' di b.
Per dimostrare che il linguaggio non è regolare, utilizzo il pumping lemma, ovvero, devo negarlo, questo significa:
\forall n \exists z \in L  |z|>=n \forall uvw : z=uvw |uv|<=n |v|>=1 \exists i : uv^i w \notin L

quindi in uv avrò tutte a mentre in w avrò tutte b, nello stesso numero.
Prendendo però i=0 uv^0w \notin L , in quanto in quanto modo so sicuramente che ci saranno n volte caratteri b ma al più n caratteri di a.
Sperò di non aver detto troppe scemenze   ciao
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.927



WWW
« Reply #4 on: 11-01-2018, 21:09:51 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa

Da dove salta fuori il numero 3???
Logged
teo998
Matricola
*
Offline Offline

Posts: 43



WWW
« Reply #5 on: 12-01-2018, 10:18:38 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa

così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca
Logged
Gerasia
Matricola
*
Offline Offline

Posts: 31
« Reply #6 on: 12-01-2018, 10:49:28 »
Quote from: teo998 on 12-01-2018, 10:18:38
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa

così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca

io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno
Logged
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11
« Reply #7 on: 12-01-2018, 12:18:01 »
Quote from: Gerasia on 12-01-2018, 10:49:28
Quote from: teo998 on 12-01-2018, 10:18:38
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa

così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca

io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno

se avesse detto, fissato un numero k era in quel modo
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.466


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


WWW
« Reply #8 on: 12-01-2018, 15:18:51 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Quale automa? Quello che non esiste?

Qui adesso risulta agevole utilizzare la funzione Ricerca (Search in alto) di questo forum, per poterti indirizzare a
questo mio interessante post a riguardo del Pumping Lemma.

Leggi, studia, e chiedi scusa pray...
« Last Edit: 12-01-2018, 15:37:55 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
teo998
Matricola
*
Offline Offline

Posts: 43



WWW
« Reply #9 on: 12-01-2018, 17:18:43 »
Quote from: Gerasia on 12-01-2018, 10:49:28

io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno

quello che hai scritto è vero; il fatto è che questo numero minimo degli stati che servono ad un automa per riconoscere un linguaggio non è noto a priori; potrebbe essere uno, cento, centomila

Per fare il ragionamento che hai fatto tu dovresti prima dimostrare che il numero minimo degli stati necessari è 3 (ma dimostrare questo non è possibile)
Logged
Pages: [1]   Go Up
Print
« precedente successivo »
Jump to: