The term “automaton” is derived from the Greek word “αὐτόματον” which means “self-acting”. An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.
An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).
Formally, a finite automaton can be represented by a 5-tuple \((Q, \Sigma, \delta, q_0, F)\) [1], where:
\(Q\) : The finite set of states.
\(\Sigma\) : The finite set of symbols, called the alphabet of the automaton.
\(\delta\) : \(Q \times \Sigma \rightarrow Q \) is the transition function.
\(q_0\) : The initial state from where any input is processed \((q_0 \in Q)\).
\(F\) : The set of final states \((F \subseteq Q)\).
Finite automaton can be classified into two types:
Alphabet: An alphabet is any finite set of symbols. For example, \(\Sigma = \{ a, b \}\), where \(a\) and \(b\) are symbols.
String: A string is a finite sequence of symbols taken from \(\Sigma\). For example, \(abba\) is a valid string on the alphabet \(\Sigma = \{a, b \}\).
Length of a String: It is the number of symbols present in a string \(S\) and it is denoted by \(|S|\). Examples:
Kleen Star: The Kleene star \(\Sigma^*\), is a unary operator on a set of symbols or strings \(\Sigma\), that gives the infinite set of all possible strings of all possible lengths over \(\Sigma\), including \(\varepsilon\). For example, if \(\Sigma = \{ a, b \}\), then \(\Sigma^* = \{ \varepsilon, a, b, aa, ab, ba, bb, aaa, \ldots \}\).
Kleen Plus: The set \(\Sigma^+\) is the infinite set of all possible strings of all possible lengths over \(\Sigma\), excluding \(\varepsilon\). For example, if \(\Sigma = \{ a, b \}\), then \(\Sigma^+ = \{ a, b, aa, ab, ba, bb, aaa, \ldots \}\).
Language: A language \(L\) is a subset of \(\Sigma^*\) for some alphabet \(\Sigma\). It can be finite or infinite. For example, if the language takes all possible strings of length 2 over \(\Sigma = \{ a, b \}\), then \(L = \{ aa, ab, ba, bb \}\).
In a DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Automaton.
A DFA is represented by a directed graph called state diagram.
[1] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to Automata Theory, Languages, and Computation, 3rd. Edition. Pearson Education, 2007. ISBN: 9780321455369