Search code examples
combinatoricsrecurrencefinite-automatadfaformal-languages

How to propose a recurrence equation for a given DFA over a set of q states?

I am trying to solve question 2 on the following link: Check out Q.2.

That is I am interested in the number N(k) of binary strings of length k accepted by the following deterministic finite automaton (source: the URL).

Finite state automaton

For example N(2)=2, as only such strings are 01 and 10. In particular I am interested in a recurrence relation for N(k).

Solution

  • The recurrence is N(k) = 2*N(k-3) + N(k-2) for k>=3, with the boundary conditions N(0)=N(1)=0 and N(2)=2.

    The reason is that given an acceptable string w (by acceptable I mean a string that the DFA accepts), you can either extend it with 11 to "remain" in the final state or add either 010 or 001 (both of length 3) to "remain" in the final state; the recurrence follows directly from these observations (think about it).

    As an example, here's the first few strings of lengths k=2,3,...,7 accepted by the automaton:

    • For k=2 the solutions are 01, 10.
    • For k=3 there are no solutions.
    • For k=4 the solutions are 0111, 1011.
    • For k=5 the solutions are 01001, 01010, 10010, 10001.
    • For k=6 the solutions are 011111, 101111.
    • For k=7 the solutions are 0100111, 0101011, 1001011, 1000111, 0111001, 0111010, 1011001, 1011010.

    We can see that the recurrence correctly counts the number of solutions:

    • N(3) = 2*N(0) + N(1) = 2*0 + 0 = 0.
    • N(4) = 2*N(1) + N(2) = 0+2 = 2.
    • N(5) = 2*N(2) + N(3) = 2*2 + 0 = 4.
    • N(6) = 2*N(3) + N(4) = 2*0 + 2 = 2.
    • N(7) = 2*N(4) + N(5) = 2*2 + 4 = 8.