Answer N(12) = 50 is correct.
In this question N(k) = "Number of words of length k that the automata accepts".
So we will start from k=2,3,4....(its already given for k=0 N(k)=0) and so on and try if we can find a recurrence relation for this.
N(2) = 2 number of words of length 2 that this automata accepts. that also mean that in 2 steps we will reach state D. the words are 01 and 10.
N(3)=0 since there is no way we can reach to D in 3 steps.
N(4)= 2 (it is only possible if we reach D in 2 ways that are 01 and 10, and then with "11" we are back to state D) correspoding words that are accepted are 0111 and 1011.
N(5)=4(only possible by first going to state D in 2 steps then coming back to D in 3 more steps in two ways "001" and "010") words accepted are 01010,01001,10010,10001.
wait a little more we are just very close to getting the recurrence relation.
N(6)=2(only possible by first going to D in two ways then with "1111" in word again coming back to state D)
Now notice that for a word to get accepted it has to end in state D(accepting state). the question reduces to in how many ways we can reach state D. Now there two ways to get to state D
1)- If you are already in D and in two step "11" you are back to state D.
2)- if you are already in D and in three steps "010" or "001" you come back to state D.
now N(4)=2 means word length is 4 and there are two ways to get to D. now in 3 more steps( with input "010" or "001") we get back to state D thtat is N(7). but wait there is another way. N(5)=4 means word length is 5 and there are 4 ways to get to D. now in 2 more steps( with input "11") we get back to state D thtat.
N(7)=2*N(4)(multipled by 2 beacuse of two ways "010" and "001")+1*N(5)(multiplied by 1 because of "11")
so N(7)=2*2+4=8
similarly N(8)=2*N(5)+N(6)= 2*4+2=10
N(9)=2*N(6)+N(7)
so the recurrence relation is
N(k)=2*N(k-3)+N(k-2)
by solving i get answer N(12)=50
ask me if you have doubt.
