Definition: A finite automaton (FA) is a 5-tuple:
M = (Q, S, R, s, F),
where
• Q is a finite set of states
• S is an input
alphabet
• R is a finite set of rules of the form:
pa
® q,
where p, q Î Q, a Î S È {e}
• s Î Q is the start state
• F Í Q is a set of final
states
Finite Automata: Definition
7/29
• Strictly mathematically, R is a
relation from Q ´
(S È {e}) to Q
• Instead of (pa, q),
however, we write the rule as pa ® q
• pa ® q
means that
with a, M can move from p to
q
• if a = e,
no symbol is read
Mathematical note on rules: