Formal Definition of a Finite Automaton (FA)

 

🤖 Formal Definition of a Finite Automaton (FA)

A Finite Automaton (FA) is a mathematical model of a system with finite memory. It processes a string of symbols and determines whether to accept or reject the string based on its transitions.

📘 Definition (from Linz and Hopcroft):

A Finite Automaton is a 5-tuple:

$$$$

Where:

Symbol	Meaning
$Q$	A finite set of states
$\Sigma$	A finite input alphabet (symbols the machine can read)
$\delta$	A transition function: $\delta: Q \times \Sigma \rightarrow Q$
$q_0$	The start state, where $q_0 \in Q$
$F$	A set of accepting (final) states, where $F \subseteq Q$

🛠️ Intuitive Meaning:

• The machine starts in initial state $q_0$.

• It reads an input string symbol by symbol.

• Based on each symbol and current state, it uses the transition function $\delta$ to move to the next state.

• After reading the entire string, if it ends in a state that is in $F$(accepting), the string is accepted; otherwise, it is rejected.

---

🧪 Example:

Let $M = (Q, \Sigma, \delta, q_0, F)$ be defined as:

• $Q = \{q_0, q_1\}$
  

• $\Sigma = \{0, 1\}$
  

• $\delta$ defined as:

$$\delta(q_0, 0) = q_0,\quad \delta(q_0, 1) = q_1,\quad \delta(q_1, 0) = q_1,\quad \delta(q_1, 1) = q_0$$

• $q_0$ is the start state

• $F = \{q_0\}$
  

👉 This FA accepts all strings with even number of 1s.