**Finite Automata In TOC**

**Finite Automata** (FA) **is a machine in TOC** that accepts all the **regular languages**. These abstract machines operate within a finite set of states and transition between these states based on inputs from a finite alphabet. Finite automata have some finite states and rules for moving from one state to another, but it depends upon the given input symbol.

**Formal definition of a Finite Automaton**

A Finite Automata contains five tuples { Q, Σ, q, F, δ }. Where

**Q**is a set of finite states.**∑**represents a finite set of symbols or alphabets.**δ**represents the transition function.**q0**is the initial state (q0 ∈ Q).**F**is a set of final states of Q (F ⊆ Q).

States, Alphabet, Transition Function, Initial State, and Final States are the **Key components** of finite automata.

**Working Of Finite Automata**

Every automata takes a language as input, processes it through some automata machines, and gives an output in the form of a set of states. The following descriptive diagram

**Types Of Finite Automata in TOC**

Following are two types of finite automata.

**1. Deterministic Finite Automata (DFA) **

In a DFA,

- For a particular input symbol, the machine goes to one state only.
- A null (ε) move is not allowed. It means the state cannot change without an input symbol.

**DFA contains 5 tuples {Q, Σ, q, F, δ}.**

- Q: Set of all states.
- Σ: Set of input symbols.
- δ: Transition Function, δ: Q X Σ →Q
- q: Initial state.
- F: Set of final state.

**2. Nondeterministic Finite Automata (NFA)**

NFA is similar to DFA except for the Null (or ε) move. In NFA, a Null move is allowed. It means the state can change without an input symbol. NFA also has similar five tuples {Q, Σ, q, F, δ} like DFA except for the transition function. The following is the NFA Transition Function.

δ: Q X (Σ U ε ) → 2 ^ Q.

**Some Important Points About DFA and NFA**

- Every DFA is NFA, but NFA is not DFA.
- In NFA and DFA, there can be multiple final states.
- DFA is used in Lexical Analysis in Compiler.
- NFA is mainly used as a theoretical concept.