Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Fondamenti di Informatica, 9 CFU => Topic started by: Gerasia on 10-01-2018, 18:10:09



Title: pumping lemma
Post by: Gerasia 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


Title: Re:pumping lemma
Post by: teo998 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


Title: Re:pumping lemma
Post by: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa


Title: Re:pumping lemma
Post by: ScavoRosario98 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


Title: Re:pumping lemma
Post by: Franco Barbanera on 11-01-2018, 21:09:51
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa

Da dove salta fuori il numero 3???


Title: Re:pumping lemma
Post by: teo998 on 12-01-2018, 10:18:38
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


Title: Re:pumping lemma
Post by: Gerasia on 12-01-2018, 10:49:28
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


Title: Re:pumping lemma
Post by: jeremy_sapienza on 12-01-2018, 12:18:01
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


Title: Re:pumping lemma
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 12-01-2018, 15:18:51
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Quale automa? Quello che non esiste? .huh

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 (http://forum.informatica.unict.it/index.php?topic=22079.msg115985#msg115985).

Leggi, studia, e chiedi scusa :pray...


Title: Re:pumping lemma
Post by: teo998 on 12-01-2018, 17:18:43

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)