finite state machine

finite state machine is a 5 tuple
M = (Q, A, T, S ,F), where
o Q --set of states = {q0, q1, q2, ….}
o A -- set of input symbols ={a,b, …, 0, 1, …}
o T --set of transitions or rules
o S -- an initial state
o F -- the final state -- could be more than one final state

Designing (drawing) FA


Deterministic Finite Automata DFA and Non Deterministic Finite Automata NFA
DFA: different input from state to different states

NFA: one input from state to different states




• Construct an Equivalent DFA from NFA.

Every DFA is an NFA, it is clear that the class of languages accepted by NFA’s includes the languages accepted by DFA’s.
To convert NFA to DFA we can carry out the following algorithm:
1- begin with {q0}, start state, and calculate ?({q0},a) for all a in ? this gives a number of new states Q-.
2- For each new states Q-, we again calculate ?(Q-,a) for all a in ? and introduce new states if necessary.
3- Repeat step2 until there are no new states.
4- Final states of new DFA are the states that contain any final state of the previous NFA.

Example:
Convert the following NFSA into equivalent DFSA

a b c
a b



M =(Q , ? , q0 , ? , F )
Q ={q0,q1,q2}
? ={a,b,c}
q0 ={q0}
F ={q1,q2}
M- = ( Q- , ? , q0 , ?- , F- )

1- ?(q0,a)?{q0,q1}
2- ? ( {q0,q1} , a )? {q0,q1}
3- ? ( {q0,q1} , b ) ? {q1,q2}
4- ? ({q1,q2} , b ) ? {q1,q2}
5- ? ( {q1,q2} , c) ? {q2}
6- ? ({q2} , c ) ? {q2}














H.W : convert the following NDFA into DFA:






H.W convert the following NFA into DFA: