Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?





Solution

In the given DFA, final states are $c$ and $g$.

First partition the states into final and non-final states:

$P_1=\{c,g\}$

$P_2=\{a,b,d,e,f,h\}$

Now minimize by checking equivalent states.

State $d$ is unreachable from the start state, so it can be ignored.

Among reachable states, equivalent groups are:

$\{a,e\}$

$\{b,h\}$

$\{f\}$

$\{c\}$

$\{g\}$

So, total minimum states are:

$5$


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...