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
- DFA
- 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 -
- It can transition to multiple state
- 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...
Top comments (0)