Stanford Automata Theory Week 1
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson. 2007.
2.2.1 Definition of a Deterministic Finite Automaton, p. 45:
A deterministic finite automaton comprises
- A finite set \(Q\) of states
- A finite set \(\Sigma\) of input symbols
- A function \(\delta:\Sigma \times Q \to Q\), the transition map
- An element \(q_0\) of \(Q\), the initial state
- A subset \(F\) of \(Q\), the final states
Let \(a = a_1 \cdots a_n \in \Sigma^n\), a string of length \(n\). Define by induction \(q_i = \delta(q_{i-1}, a_i)\) for \(1 \leq i \leq n\). (The induction is on \(n\), not on \(i\).) The string is said to be accepted by \(A\) if \(q_n \in F\), and rejected by \(A\) if \(q_n \not \in F\).
An empty string \(\epsilon \in \Sigma^0\) is accepted by \(A\) if \(q_0 \in F\) and rejected by \(A\) is \(q_0 \not \in F\).