How to calculate This recurrence ?

Question

.

The finite automaton below: accepts no word of length zero, no word of length one, and only two words of length two (01 and 10). There is a fairly simple recurrence equation for the number N(k) of words of length k that this automaton accepts. Discover this recurrence and demonstrate your understanding by identifying the correct value of N(k) for some particular k. Note: the recurrence does not have an easy-to-use closed form, so you will have to compute the first few values by hand. You do not have to compute N(k) for any k greater than 14.

	a)	N(14) = 280
	b)	N(11) = 76
	c)	N(13) = 2730
	d)	N(11) = 32

Answer 1

No. That will be more complex. We have to ensure we do not count any duplicate string here.

Consider your first recurrence.

D(X)= D(X-2)+D(X-3)

The first term - D(X-2) accounts for strings of length X-2, and we append "11" to them to get strings of length X.

Now, D(X-3) accounts for strings of length X-3. We can append, either "001" or "010" to them. Will either be adding a repeated string we calculated in above step? No. because they all end in "11". So, our recurrence will be

D(X)= D(X-2) + 2D(X-3).

D(0) = 0.

D(1) = 0.

D(2) = 2.

D(3) = 0.

D(4) = 2.

D(5) = 4.

D(6) = 2.

D(7) = 8.

D(8) = 10.

D(9) = 12.

D(10) = 26.

D(11) = 32.

D(12) = 50.

D(13) = 84.

D(14) = 114.

Comments

@arjun sir is this recurrence from the STATE D to get back to D?

---

Sir you gave a recurrence relation from D so we need to multiply it with 2 as you can reach A to D in 2 ways 01 or 10 so ...but no options are matching if i multiply by 2 plz clarify

---

No, the recurrence is for the no. of strings accepted - so no. of unique paths from start state A to D.

---

I got it arjun sir actual your equation and my equation represent the same

N(K)=2*D(K-2)=2*D(K-4)+4*D(K-5)=N(K-2)+2*N(K-3)

N(K-2)=2*D(K-4)

N(K-3)=2*D(K-5)

D(X)= D(X-2)+2*D(X-3)

N(K-2)=2*D(K-4)=2*D(K-6)+4*D(K-7)

N(K-3)=2*D(K-5)=2*D(K-7)+4*D(K-8)

N(K)=N(K-2)+2*N(K-3)=2*D(K-6)+6*D(K-7)+4*D(K-8)

Answer 2

my approach was like you can reach the final state D in 2 steps so i took recurrence relation from D as

D(X)= D(X-2)+D(X-3)---as later again after reaching D to get back to D either 2 or 3 inputs are needed

[EDIT] as  said by arjun sir the correct equation will be D(X)= D(X-2)+2*D(X-3)

but to reach D from A there are two paths so

N(K)=2*D(K-2)----as two paths after that two letters are consumed from the input

so the final correct equations will be 

N(K)=2*D(K-2)

D(X)= D(X-2)+2*D(X-3)

so D(9)=16 and N(11)=2*D(9)=32

so answer is D

Comments

@arjun sir plz verify i think this should be the correct answer