Aspire's Library

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

Previous Year Question (PYQs)



In the $\epsilon$-NFA, $M=({q_0,q_1,q_2,q_3},{a},\delta,q_0,{q_3})$ where $\delta$ is given in the transition table below, what is the minimum length of string to reach to the final state?
   $\epsilon$ 

$a$ 
 $q_0$ {$q_1$}{ } 
 $q_1${$q_2$}  { }
 $q_2${ } {$q_2 , $ $q_3$ }
 $q_3${} {} 






Solution

Initial state is:

$q_0$

From $q_0$, using $\epsilon$ move:

$q_0 \xrightarrow{\epsilon} q_1$

From $q_1$, again using $\epsilon$ move:

$q_1 \xrightarrow{\epsilon} q_2$

So, without reading any input symbol, we can reach:

$q_2$

But final state is:

$q_3$

Now from $q_2$, on input symbol $a$:

$q_2 \xrightarrow{a} {q_2,q_3}$

So, after reading one $a$, we can reach final state $q_3$.

Therefore, the minimum string is:

$a$

Length of $a$ is:

$1$



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