# Definition- Finite Automata

Definition-Finite Automata is the important topic of the Theory Of Computation. Theory Of Computation is the Important subject of the Computer.

## Definition-Finite Automata

A finite Automata or finite state machine is a 5-tuple(Q,∑,q_{0}, A,δ) where,

Q is finite set of states;

∑ is finite alphabet of input symbols;

q_{0 }∈ Q (Initial state); A (set of accepting states);

δ is a function from Q×∑àQ(Transition function);

For any element q of Q and any symbol a ∈ ∑, we interpret δ (q, a) as the state to which the Finite Automata moves, if it is in state q and receives the input a.

**Application of finite automata **

A finite automaton is used to solve several common types of the computer algorithm. Some of them are:

- Design of digital circuit.
- String matching.
- Communication protocols for information exchange.

The lexical analysis phase of a compiler.

### The Extended transition function δ* for FA

Let M= (Q,∑,q_{0}, A,δ) be a Finite Automata. We define the function δ*: Q×∑*àQ as follow:

1) For any q ∈ Q, δ*(q,^)=q

2) For any q ∈ Q, y ∈ ∑*, and a ∈ ∑ δ*(q, ya)= δ(δ*(q, y), a)

Example:

**Fig -Finite Automata **

δ*(q,abc)

δ(δ*(q,ab),c)

δ(δ*( δ*(q,a),b),c)

δ(δ(δ* (q,^a),b),c)

δ(δ(δ(δ*(q,^),a),b),c)

δ(δ(δ(q,a),b),c)

δ(δ(q1,b),c)

δ(q_{2},c)

q3

### Draw Finite Automata for following: **Definition-Finite Automata**

**The string with next to last symbol as 0.****Fig – Finite Automata for next to the last symbol as 0**

**The string with a number of 0s and number of 1s is odd.****Fig -Finite Automata for number of 0s and number of 1s are odd**

**The string ending in 10 or 11.Fig – Finite Automata for string ending in 10 or **

**The string corresponding to Regular expression {00}*{11}*.Fig – Finite Automata for {00}*{11}* **

**(a+b)*baaa.****Fig – Finite Automata for (a+b)*baaa**

#### Define Dead End State: Definition-Finite Automata

** **Dead state is those non-accepting states whose transitions for every input symbols terminate on themselves.Ex: all strings of length at most 3. The string of length >3 should be rejected by a dead state or a failure state. In above example dead state is q_{4}.

**Related Terms**

Theory of Computation, PDA – CFG, Mathematical Induction, Regular language & Expression

## Leave a Reply