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?

possible answers

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

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

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

4) q1 and q4 will be distingushed on the second pass.

Solution

q1 and q4 will be distinguishable on second pass

This is so because after starting from the initial state, q0, and scanning the input \'b\' we reach the state q1.

Now from q1we have 2 possibilities, either the next symbol nam be a or b, if it is a, it will move to q2 and reach finish symbol and if it is b it moves to q3, from where we can scan a and reach q4 which is also finish state.

(q0,b) :- q1

(q1,b) :- q3

(q3,a) :- q4.

therefore after reaching q1 it requires two passes to reach q4.