Automata

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.

Finite Automaton

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:

• Deterministic Finite Automaton (DFA)
• Non-deterministic Finite Automaton (NFA)

Additional Terminology

• 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:

  • If \(S = abba\), \(|S|= 4\)
  • If \(|S|= 0\), it is called an empty string and is denoted by \(\varepsilon\).

• 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 \}\).

Deterministic Finite Automaton (DFA)

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.

• The vertices represent the states.
• The arcs labeled with an input alphabet show the transitions.
• The initial state is denoted by an empty single incoming arc.
• The final state is indicated by a double circle.

References

• [1] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to Automata Theory, Languages, and Computation, 3rd. Edition. Pearson Education, 2007. ISBN: 9780321455369