Newsgroup: it.scienza.informatica
Titolo: Finite Automata

Non riesco a capire un passaggio sul libro di Straubing. Senza capire 
quello è inutile che vada avanti.
Premetto che A è sempre un alfabeto.
______________
A nondeterministic finite automaton is a quadruple
M = (Q, i, F, E)
where Q is a finite set, i in Q, F <= Q, and E <= Q x A x Q. We call Q 
the set of states of the automaton, i the initial state, F the set of 
final states, and E the set of edges. A sequence of edges
(q_0, a_1, q_1)(q_1, a_2, q_2)... (q_{k-1}, a_k, q_k)
is called a path in M from q_0 to q_k, and the word
a_1...a_k
is called the label of the path. We make the convention that for all q 
in Q there is a path from q to q whose label is 1. A word w in A* is 
accepted by the automaton if there is a path labelled w from i to some q 
in F. The set of all words accepted by M is called the language 
recognized by M. A language L <= A* is said to be regular if it is 
recognized by some nondeterministic finite automaton. As our terminology 
indicates, we view an automaton as a directed graph whose vertices are 
the states and whose edges are labelled by elements of A. We will use 
this graphical interpretation in the figures in this book: We indicate 
the vertices by circles, and the edges by labelled arrows. We will use 
double circles to indicate which states are the final states, and 
indicate the initial state with an entering arrow.
--------------
Fin qui tutto bene. Ho riportato ugualmente il testo per una questione 
di continuità.
______________
A deterministic finite automaton is a quadruple
M = (Q, i, F, l) where Q, i, and F are as above, and l is a map from Q x 
A into A (called the next state function.)
--------------
Questa cosa già non mi è chiara. Non dovrebbe essere QxA -> Q?
Comunque è una definizione quindi l'accetto.
______________
If q in Q and a in A we will usually write qa or q.a in place of l(q, 
a). We then define qw for q in A and w in A* by induction on |w| as follows:
--------------
Cosa vuol dire induzione su |w|? Si può procedere per induzione su una 
cardinalità? (A* è l'insieme delle parole.)
______________
q.1 = q,
q.(wa) = (qw).a,
for all a in A. It is easy to see that for all w_1, w_2 in A*,
q(w_1w_2) = (qw_1)w_2.
--------------
Ma cosa c'entra tutto questo? q non deve appartenere a Q??? Perché 
appartiene ad A? Gli stati vengono indicati tramite l'alfabeto A???
______________
A word w is accepted by M if and only if iw in F. We again define the 
language recognized by M as
--------------
Come sopra.
______________
the set of all words that M accepts. The deterministic automaton is the 
same thing as the nondeterministic automaton
(Q,i,F, {(q,a,qa) : q in A, a in A}),
and thus the language it recognizes is regular. Observe that in this 
view, the deterministic
--------------
Continuo a non capire perché q è in A, quando dovrebbe essere in Q.
______________
automata are characterized by the property that for all q in Q and w in 
A*, there is exactly one
path labelled w that begins at q.
--------------
Kiuhnm

 path labelled w that begins at q.
qui va bene, infatti q adesso sta in Q

 Continuo a non capire perché q è in A, quando dovrebbe essere in Q.
Infatti.
q appartiene a Q.
Probabilmente qui sta ripetendo pari pari quello che ha già fatto in
generale per gli automi non deterministici.
Il copia e incolla non deve essergli riuscito bene... :-)

 A word w is accepted by M if and only if iw in F. We again define the 
[8<]
Ciao
-- 
Sandro Tosi (aka Morpheus, matrixhasu)
My (little) site: 
http://matrixhasu.altervista.org/

Grazie a tutti!
Kiuhnm

 e' disponibile al colloquio, anche col professore.
E come faccio a sapere che la definizione è sbagliata?
Perché credi che abbia scritto sul ng? Evidentemente avevo qualche sospetto.
Devi sapere che quella def. compare a pag. 2 del libro e l'autore non dà 
alcuna definizione di "deterministico", né parla di nastri.
Senza alcuna informazione posso sapere che una definizione è sbagliata?
Il sospetto mi è nato soltanto dando un'interpretazione intuitiva al 
termine "deterministico".
Kiuhnm

 termine "deterministico".
Visto l'argomento direi che sei uno studente universitario, e come tale 
dovresti avere a disposizione una biblioteca che contiene dei testi di 
informatica: consultare altri libri ed altre fonti e' un atto 
*fondamentale* della crescita di uno "scienziato"; si', informatica sta 
sotto SMFN e quindi, tecnicamente, si diventa scienziati... ;))


 Visto l'argomento direi che sei uno studente universitario, e come tale 
No, studio da solo.
Comunque non hai considerato il fatto che i ng /sono/ una risorsa.
Non ho scritto sul ng perché disperato, ma perché ho pensato di 
risparmiare tempo (e così è stato). Intanto ho studiato le mille altre 
cose che ho in programma.
Ho scoperto che quel libro è tutt'altro che introduttivo: è rivolto ai 
ricercatori :O
Per il momento ho ripiegato su uno dei classici testi universitari e le 
pagine scorrono senza problemi. In seguito riaffronterò il libro di 
Straubing.
Kiuhnm