**Introduction To Finite Automata**

Finite Automata (FA) is a machine which accepts all the regular languages. It is used to recognize the patterns. It is also called finite state machine.

**Working Of Finite Automata**

- The finite automata machine contains five tuple or elements.
- It has some finite states and rules for moving from one state to another but it depends upon the given input symbol.

Basic diagram is given below

A Finite Automata can be defined through its 5 tuples { Q, Σ, q, F, δ }. Where

**Q : Finite set of states.****Σ : set of Input Symbols.****q : Initial state.****F : set of Final States.****δ : Transition Function.**

**Types Of Finite Automata**

FA is characterized into two types:

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

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

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

Q : set of all states.

Σ : set of input symbols.

q : Initial state.

F : set of final state.

δ : Transition Function, δ : Q X Σ –> Q.

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

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

**δ: 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 mostly used as theoretical concept.