Straubing: Finite Automata

I hope this is the right ng.

I have some problem with Straubing's Finite Automata book.
I cannot understand the definition of DFA:

>>>>>>>>>>>>
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.

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.)
<<<<<<<<<<<<

Here is the problem: I would have expected QxA->Q.
Therefore, what follows is similarly incomprehensible to me.

>>>>>>>>>>>>
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:
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.
A word w is accepted by M if and only if iw in F. We again define the language recognized by M as
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
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.
<<<<<<<<<<<<

Thanks, Kiuhnm
.

Relevant Pages

  • Re: map with polymorphic key???
    ... > I am trying to implement various kinds of finite automaton simulators; ... Use a pointer (or preferably a smart pointer) for the key and a comparison ... Whether that's good design for your application I couldn't say but it will ...
    (comp.lang.cpp)
  • Re: The state machine of no input
    ... >> How did your textbook define what it means for an automaton to ... >> that an input string is in the language? ... > accepting state depends upon which state is chosen as the initial state. ... > Each state transition is well defined but initiated by the clock, ...
    (sci.math)
  • Re: fsa: compleixity and frequency
    ... The size of a FSA is the number of states in ... |(i.e. there are many FSA which accept a given language). ... if we started the automaton in that state. ... state have to be the strings in the prefix language ...
    (comp.theory)
  • Re: Context Free Grammer
    ... Working off of your example in a more regular way, ... S for Q, you get a grammar for the language in question. ... The automaton is drawn as the Cartesian product of the respective ...
    (comp.lang.java)