 # 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)$$ , 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)

• 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

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