In the process of applying our algorithm for determining dis

In the process of applying our algorithm for determining distinguishability of states, which of the following is true for the FA shown below?

  
A) q1 and q4 will be distinguished on the second pass.

  
B) q1 and q4 will be distinguished on the third pass.

  
C) q1 and q4 will be distinguished on the first pass.

  
D) q1 and q4 will be found to be indistinguishable.

Solution

B) q1 and q4 will be distinguished on the third pass.

It takes string of at least 3 charcters (bba) to reach q4 where we will know that q4 is a final state and is distinguishable from q1 which is non final state. Till third pass both are non distinguishable.