Finite Automata

It is a abstract machine is used to recognized pattern in input sequence . It is formed to understand regular languages in computer science .

It consists of states , Transition and input symbols . It process each symbol step by step .

If the machine ends in an accepting state after processing the input , it is accepted . otherwise it is rejected .

Finite automata is two types

1. DFA
2. NFA DFA : One input -> Output one state Every input must have transition state .

Example :
Construct a DFA that accepts all strings ending with ‘a’.

Given:

Σ = {a, b},

Q = {q0, q1},

F = {q1}

State\Symbol a b
q0 q1 q0
q1 q1 q0
Non-Deterministic Finite Automata (NFA):
Similar to DFA but -

1. It can transition to multiple state
2. It can have Null moves , Machine can change state without consuming input

Comparison of DFA and NFA
Although NFAs appear more flexible, they do not have more computational power than DFAs.

Construct a dfa which accepts set of all strings over the s = {a,b} , where each string start with an 'a'

L(M) = {w|w starts with an 'a'}

A = {a,b}
L = {a,aa,ab,aaa,ava ,abb .... }
-> Initial State = Accept state

To be continued...