Aspire's Library

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

Previous Year Question (PYQs)



How many states are there in a minimum state automata equivalent to regular expression given below?

Regular expression is $a^*b(a+b)$






Solution

The regular expression is

$a^*b(a+b)$

It means:

Any number of $a$'s, followed by one $b$, followed by either $a$ or $b$.

So, strings accepted are like:

$ba,\ bb,\ aba,\ abb,\ aaba,\ aabb$

Minimum DFA states needed:

State $q_0$: Initial state, reads any number of $a$'s.
State $q_1$: After reading required $b$.
State $q_2$: Final state after reading last symbol $a$ or $b$.
State $q_d$: Dead state for extra or invalid symbols.

Thus, total minimum states are

$4$



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...