Finite automata (FAs)

Finite Automata (FAs)

Finite Automata (FAs) are mathematical models used to recognize regular languages. They are abstract machines that consist of a finite set of states and transition rules, allowing them to process strings of symbols from a given alphabet. Finite automata are essential in the study of automata theory, as they provide the foundation for understanding computation in terms of state transitions.

Key Concepts of Finite Automata

A finite automaton can be seen as a directed graph where:

• The nodes represent states.
• The directed edges represent transitions between states based on input symbols.

The automaton processes an input string and moves from one state to another based on the input symbols. If the machine ends in a final (accepting) state after reading the entire input, the string is accepted; otherwise, it is rejected.

Components of Finite Automata

A finite automaton is formally defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

1. Q: A finite set of states.
2. Σ (Sigma): A finite set of input symbols, also called the alphabet.
3. δ (delta): The transition function, which specifies the state transitions. It is defined as: $$\delta: Q \times \Sigma \rightarrow Q$$ That is, for a given state and input symbol, it returns the next state.
4. q₀: The initial state from which the machine starts processing the input string. $q_0 \in Q$.
5. F: The set of accepting (final) states, where $F \subseteq Q$. If the automaton ends in an accepting state after processing the input, the string is accepted.

Types of Finite Automata

There are two primary types of finite automata: Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA).

---

1. Deterministic Finite Automata (DFA)

A Deterministic Finite Automaton (DFA) is a finite automaton where, for each state and input symbol, there is exactly one transition to a next state. There are no ambiguities in the state transitions.

Formal Definition of a DFA

A DFA is a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$ is the set of states.
• $\Sigma$ is the alphabet (set of input symbols).
• $\delta: Q \times \Sigma \rightarrow Q$ is the transition function, which assigns exactly one state to each state-symbol pair.
• $q_0$ is the initial state.
• $F$ is the set of accepting (final) states.

Example of DFA

Consider a DFA that accepts binary strings ending with '01':

• States: $Q = \{q_0, q_1, q_2\}$

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

• Transition Function:

  • $\delta(q_0, 0) = q_0$ (stays in $q_0$ when reading '0')
  • $\delta(q_0, 1) = q_1$
  • $\delta(q_1, 0) = q_2$
  • $\delta(q_1, 1) = q_1$ (stays in $q_1$ when reading '1')
  • $\delta(q_2, 0) = q_0$ (goes to $q_0$ on reading '0')
  • $\delta(q_2, 1) = q_1$

• Initial State: $q_0$

• Accepting State: $F = \{q_2\}$

This DFA accepts strings like "01", "101", "1101", but rejects strings like "0", "111", and "100".

Properties of DFAs:

• Deterministic: There is exactly one transition for each state and input symbol.
• Efficiency: DFAs are efficient because they process input in linear time, as there is only one state transition per input symbol.

---

2. Nondeterministic Finite Automata (NFA)

A Nondeterministic Finite Automaton (NFA) is a finite automaton where, for a given state and input symbol, there can be multiple possible next states, or even no next state at all. In other words, an NFA may have several transitions for a given input symbol.

Formal Definition of an NFA

An NFA is also defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$ is the set of states.
• $\Sigma$ is the alphabet.
• $\delta: Q \times \Sigma \rightarrow 2^Q$ is the transition function, which maps a state-symbol pair to a set of states (not a single state).
• $q_0$ is the initial state.
• $F$ is the set of accepting states.

Example of NFA

Consider an NFA that accepts strings containing "ab" (i.e., the substring "ab" appears anywhere in the string).

• States: $Q = \{q_0, q_1, q_2\}$

• Alphabet: $\Sigma = \{a, b\}$

• Transition Function:

  • $\delta(q_0, a) = \{q_0, q_1\}$ (either stays in $q_0$ or transitions to $q_1$ on reading 'a')
  • $\delta(q_0, b) = \{q_0\}$
  • $\delta(q_1, a) = \{q_1\}$
  • $\delta(q_1, b) = \{q_2\}$ (transitions to $q_2$ on reading 'b')
  • $\delta(q_2, a) = \{q_2\}$
  • $\delta(q_2, b) = \{q_2\}$

• Initial State: $q_0$

• Accepting State: $F = \{q_2\}$

This NFA accepts strings like "ab", "aab", "abab", and "baab".

Properties of NFAs:

• Nondeterministic: There can be multiple possible next states for a given state and input symbol, or even no next state.
• Parallel Exploration: Conceptually, an NFA can explore all possible state transitions simultaneously, accepting a string if there is at least one path that leads to an accepting state.

---

3. Epsilon-Nondeterministic Finite Automaton (ε-NFA)

An ε-NFA is a variant of an NFA where, in addition to regular transitions, the machine can also transition from one state to another without consuming any input symbols, using ε (epsilon) transitions.

Formal Definition of ε-NFA

An ε-NFA is defined as:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$ is the set of states.
• $\Sigma$ is the alphabet.
• $\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow 2^Q$ is the transition function, which allows transitions on both input symbols and epsilon (ε).
• $q_0$ is the initial state.
• $F$ is the set of accepting states.

Acceptance by Finite Automata

• DFA: A string is accepted if, after processing all the input symbols, the DFA ends in one of its accepting states.
• NFA: A string is accepted if there exists at least one path through the NFA that ends in an accepting state after processing all input symbols.
• ε-NFA: A string is accepted if there exists at least one path, considering both regular transitions and epsilon transitions, that ends in an accepting state.

---

Equivalence of DFAs and NFAs

• Recognizing the Same Class of Languages: Despite the differences in how transitions are handled, both DFAs and NFAs recognize the same class of languages: the regular languages.
• Conversion: Any NFA can be converted into an equivalent DFA through a process called subset construction. While the DFA may have more states, both machines recognize the same language.

---

Conclusion

Finite Automata (FAs) are fundamental models for computation and form the basis of regular language theory. DFAs and NFAs are different types of finite automata, with DFAs having deterministic transitions and NFAs allowing for nondeterministic behavior. Despite their differences, both types of automata recognize regular languages, and any NFA can be converted into an equivalent DFA. Finite automata are widely used in practical applications such as lexical analysis, pattern matching, and text processing.