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$ | {} | {} |
🎥 Video solution / Text Solution of this question is given below:
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$