Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Fondamenti di Informatica, 9 CFU => Topic started by: J0SepH_ on 30-10-2018, 11:23:27



Title: Domanda Automi
Post by: J0SepH_ on 30-10-2018, 11:23:27
È possibile un ASFD con 2 o più stati finali? (o di accettazione)


Title: Re:Domanda Automi
Post by: Franco Barbanera on 30-10-2018, 12:42:33
È possibile un ASFD con 2 o più stati finali? (o di accettazione)

Qual e' la definizione di ASFD?

Scrivila o dimmi dove trovarla nel testo.


Title: Re:Domanda Automi
Post by: J0SepH_ on 30-10-2018, 13:05:17
Definizione formale

Un Automa a Stati Finiti Deterministico è una quintupla in cui A(automa)={∑(alfabeto), Q(Insieme degli stati es q1,q2), δ (funzione di transizione), q0(stato iniziale) F(stato finale)}.



Title: Re:Domanda Automi
Post by: Franco Barbanera on 30-10-2018, 14:00:23
Definizione formale

Un Automa a Stati Finiti Deterministico è una quintupla in cui A(automa)={∑(alfabeto), Q(Insieme degli stati es q1,q2), δ (funzione di transizione), q0(stato iniziale) F(stato finale)}.

Dove l'hai studiata questa definizione?


Title: Re:Domanda Automi
Post by: J0SepH_ on 30-10-2018, 17:42:52
È presente nei miei appunti ho sbagliato a copiarla, possono essere presenti 2 o più stati di accettazione, ho verificato.


Title: Re:Domanda Automi
Post by: Franco Barbanera on 30-10-2018, 18:38:18
È presente nei miei appunti ho sbagliato a copiarla, possono essere presenti 2 o più stati di accettazione, ho verificato.

Una curiosita': dove hai verificato?


Title: Re:Domanda Automi
Post by: J0SepH_ on 30-10-2018, 20:57:24
Sui miei stessi  appunti, in pratica sopra dove ho scritto "F(stato finale)" in realtà è: "F(insieme degli stati finali)" in cui F⊆Q(quest'ultimo insieme degli stati) quindi ne ho dedotto che gli stati finali posso essere più di 2.
"ho verificato", nel senso che ho verificato/confrontato con gli appunti di un collega.


Title: Re:Domanda Automi
Post by: Franco Barbanera on 30-10-2018, 21:18:47
Bene.

Per fortuna stiamo comunicando per iscritto, cosi' non si sentono le mie urla...


Qualcuno ti ha mai fatto presente che esistono i LIBRI !?!??

Che NON SI STUDIA SOLO SUGLI APPUNTI ??!!??

Che per risolvere il tuo problema sarebbe bastato prendere il testo di riferimento
per la parte di Linguaggi Formali
[AAG] G. Ausiello, F. d'Amore, G. Gambosi. Linguaggi, Modelli, Complessita' (pdf file)
presente nella pagina del programma
http://www.dmi.unict.it/~barba/FONDAMENTI/PROGRAMMI-TESTI/programmaAAcorrente.html
e leggere la Definizione 3.1 ??!??

Che gli appunti servono per ricordare le idee generali, le intuizioni sottostanti alle nozioni formali,
ma che poi le definizioni i teoremi e le varie formalizzazioni dei concetti discussi in aula
SI STUDIANO SUL TESTO??!??


Un cordiale saluto
FB


Title: Re:Domanda Automi
Post by: J0SepH_ on 31-10-2018, 14:56:11
Ok.
Per evitare di scrivere un altro Topic ne approfitto per un'altra domanda. Nelle definizione 2.3 al Capitolo 2 della Logica Martini (http://www.dmi.unict.it/~barba/FONDAMENTI/PROGRAMMI-TESTI/READING-MATERIAL/LOGICA/logicaMartini.pdf)
 
non ho capito il terzo punto, cosa vuol significare? che un insieme di fbf  ∈  Rj (con j ∈ I [indici suppongo]) viene sostituito con una fbf presente nel sistema formale D?    


Title: Re:Domanda Automi
Post by: Franco Barbanera on 31-10-2018, 16:04:52
Quello che tu chiami insieme e' una ennupla di fbf, in particolare una ennupla di nj formule ben formate.

Se una ennupla appartiene ad una regola di inferenza, l'ultimo elemento dell'ennupla si chiama
conclusione e i precedenti si chiamano premesse.
Il punto in questione dice che  una fbf in una derivazione corretta puo' essere
la conclusione di una regola di inferenza se le premesse della regola sono gia'
presenti nella derivazione.

Esempio:
Gli elementi della relazione (regola di inferenza) modus ponens sono
triple della forma (A, A->B,B)
Il punto in questione dice che puoi avere B in una derivazione corretta
se prima di B ci sono due formule, A e A->B




Title: Re:Domanda Automi
Post by: J0SepH_ on 31-10-2018, 16:19:10
Grazie, quindi in pratica hnj-1 sta a significare che appunto una delle formule non va rappresentata nell'ennupla di Rj?
Nell'esempio che ha scritto lei, consideriamo solo A e A-->B nell'ennupla di Rj in quanto B è la nostra conclusione e dobbiamo quindi "toglierla" [hnj-1].
                                    


Title: Re:Domanda Automi
Post by: Franco Barbanera on 31-10-2018, 20:20:44
Quote
quindi in pratica hnj-1 sta a significare che appunto una delle formule non va rappresentata nell'ennupla di Rj?
No.
Significa che se la conclusione della regola (la formula piu' a destra nell'ennupla) e' nella derivazione,
allora le sue premesse (tutte le formule nell'ennupla meno quella a destra) debbono essere
gia' presenti nella derivazione.


Title: Re:Domanda Automi
Post by: Franco Barbanera on 31-10-2018, 20:22:59
Quote
Nell'esempio che ha scritto lei, consideriamo solo A e A-->B nell'ennupla di Rj in quanto B è la nostra conclusione e dobbiamo quindi "toglierla" [hnj-1].

In questo esempio significa che se hai B nella derivazione (dove B e' l'ultimo elemento dell'ennupla (A,A->B,B)  )
allora prima di B, nella derivazione,  devi avere A  e A-> B.


Title: Re:Domanda Automi
Post by: J0SepH_ on 01-11-2018, 10:21:51
ho capito, grazie prof


Title: Re:Domanda Automi
Post by: Franco Barbanera on 01-11-2018, 11:38:59
 :-OK
 .ciaociao


Title: Re:Domanda Automi
Post by: J0SepH_ on 02-11-2018, 02:04:26
Mi scuso se la disturbo stavo studiando sempre la parte dei sistemi formali e (convinto di aver capito) mi stavo avviando ad alcuni esercizi presenti nel suo sito in particolare il numero 100 (http://www.dmi.unict.it/~barba/FONDAMENTI/ESERCIZI/LOGICA/esercizi.html).
L'esercizio in questione si rifà al sitema formale qui presente (http://www.dmi.unict.it/~barba/FONDAMENTI/PROGRAMMI-TESTI/READING-MATERIAL/LOGICA/logicaMartini.pdf) Pag 7 Capitolo 2

Potrebbe spiegarmi come faccio dal termine (ksk)(kkk)=sk applicando l'assioma [Axk] ((kP)Q)=P ad ottenere questo:
(risposte copitate dalla soluzione da lei fornita)

1. ksk = s                 (Axk)
2. kkk = k                 (Axk)
3. (ksk)(kkk)=(ksk)(kkk)   (assioma rifl)
4. (ksk)(kkk)=s(kkk)       (cong2)1.3.
5. (ksk)(kkk)=sk           (cong1)4.2.

Dalle 4 alla 5 ci sono benomale, ma dalla 1 alla 3 non ho capito.




Title: Re:Domanda Automi
Post by: Franco Barbanera on 02-11-2018, 10:30:26
1. ksk = s                 (Axk)

Questo e' un assioma (Axk).
Infatti tutte le fbf della forma ((kP)Q) = P sono assiomi Axk.
In questo caso innanzitutto occorre aver chiaro che scrivere  ksk equivale a scrivere
(per la convenzione che ci permette di non scrivere troppe parentesi)
((ks)k)
Quindi  ksk = s e' un assioma Axk perche' s gioca il ruolo di P, e k quello di Q.


2. kkk = k                 (Axk)

Sempre assioma Axk, poiche' e' come se avessimo scritto
((kk)k) = k
con il secondo k da sinistra che gioca il ruolo di P w il trezo che cgioca il ruolo di Q


3. (ksk)(kkk)=(ksk)(kkk)   (assioma rifl)

Ogni fbf della forma P=P e' un assioma di riflessivita' (ricordiamo ancora una volta, come detto in aula,
che gli assiomi in realta' sono "schemi di assioma" cioe' ogni fbf con quella struttura e' un assioma).
In questo caso il ruolo di P  viene giocato dal termine (ksk)(kkk).


Title: Re:Domanda Automi
Post by: J0SepH_ on 02-11-2018, 12:05:26
Ho capito, un'ultima cosa, sempre su questa pagina del capitolo.

Nel primo esempio: "una deduzione in CL: dimostriamo che |-cl (((sk)k)k)=k"
in particolare al punto 2:
((kk)(kk))=k           Axk con P ≡k e Q ≡(kk)

mi può spiegare perchè il segno " ≡" e perchè lo poniamo a Q e P? e poi non la disturbo più
 


Title: Re:Domanda Automi
Post by: Franco Barbanera on 02-11-2018, 15:35:48
Quel segno, utilizzato spesso per indicare una congruenza,
viene anche utilizzato per indicare coincidenza, identita'.
Nel nostro caso per indicare
"definamo P come k"
o, nel nostro modo informale di dire
"k gioca il ruolo di P".

Infatti l'assioma Axk e'
((kP)Q = P
e in questo caso, se come P prendiamo k e come Q prendiamo (kk), abbiamo
((kk)(kk))=k


Title: Re:Domanda Automi
Post by: J0SepH_ on 02-11-2018, 18:06:28
ok grazie mille


Title: Re:Domanda Automi
Post by: J0SepH_ on 06-11-2018, 16:56:16
Prof mi scusi evito di scrivere altri post, le volevo chiedere nella logica martini mi saprebbe spiegare a pagine 6 la seconda osservazione ossia la reciproca non derivabilità di un insieme di assiomi?

http://www.dmi.unict.it/~barba/FONDAMENTI/PROGRAMMI-TESTI/READING-MATERIAL/LOGICA/logicaMartini.pdf


Title: Re:Domanda Automi
Post by: Franco Barbanera on 06-11-2018, 17:30:40
Prof mi scusi evito di scrivere altri post, le volevo chiedere nella logica martini mi saprebbe spiegare a pagine 6 la seconda osservazione ossia la reciproca non derivabilità di un insieme di assiomi?

http://www.dmi.unict.it/~barba/FONDAMENTI/PROGRAMMI-TESTI/READING-MATERIAL/LOGICA/logicaMartini.pdf

Salta pure quell'osservazione. Occorre avere molto ben chiaro tutto quanto per riuscire a darle un senso.
Puoi evitare di leggerla.


Title: Re:Domanda Automi
Post by: J0SepH_ on 06-11-2018, 17:47:55
ho capito ma quando dice "Occorre avere molto ben chiaro tutto quanto" intende dire occore avere ben chiaro tutto il capitolo 2 o in generale tutta la logica?