No of string accepted by a finite automata

Question

Answer 1

The possible ways to create an acceptable string of length $k$ are:

• Start with an acceptable string of length $k-3$, and take the $D\to ACD$ path.
• Start with an acceptable string of length $k-3$, and take the $D\to ABD$ path.
• Start with an acceptable string of length $k-2$, and take the $D\to BD$ path.

Thus, we achieve the recurrence relation given below:

$$N(k) = \underbrace{N \Bigl (k-3 \Bigr )}_{D\to ACD} + \overbrace{N \Bigl (k-3 \Bigr )}^{D\to ABD} + \underbrace{N \Bigl (k-2 \Bigr )}_{D\to BD}$$

$$\boxed{\displaystyle N(k) = 2N \Bigl (k-3 \Bigr ) + N \Bigl (k-2 \Bigr )}$$

The sequence for $N(k)$ thus generated is
$$\small 0, 0, 2, 0, 2, 4, 2, 8, 10, 12, 26, 32, 50, 84, 114, 184, 282, 412, 650, 976, 1474, \ldots$$

http://ideone.com/JtmMW1

So, $N(11)=32$ is the correct answer.

Comments

If you are not able to frame the recurrence relation then you may use the below explained procedure as a work around.

Suppose function f(x, i) calculates how many there are binary input strings that gets us to state x on i-th input symbol. So  f(B, 0)  = f(C, 0) = f(D, 0) = 0 since A is the starting state and an empty string will not get us any further from starting state and similarly reasoning we get that f(A, 0) = 1, since there is an empty binary string that gets us to state A. Notice that if we would knew how many there are ways to get to B and C and we would have single input character left then the answer would be:
ways to get to D = ways to get to B + ways to get to C. Using our function we can describe that like:
f(D, i) = f(B, i - 1) + f(C, i - 1)
and for other states:
f(A, i) = f(D, i - 1)
f(B, i) = f(A, i - 1) + f(D, i - 1)
f(C, i) = f(A, i - 1).

Now we are left with simple arithmetics, below are illiustrated function f values (i is input string length): 

 i   A   B   C   D
0   1   0    0   0

1   0   1    1   0

2   0   0    0   2

3   2   2    0   0

4   0   2    2   2

5   2   2    0   4

6   4   6    2   2

7   2   6    4   8

8   8 10    2 10

9 10 18    8 12
...

Answer to our problem is f(D, i), where i is input string length provided in options.

Also this method provides information on all the states instead of only final state.

---

@Mari: Did you mean to comment on Anurag's answer?

---

The comment has nothing to do with your answer.. Its just the way I used to solve it.. posted it as a comment as you have already posted the answer :)

Answer 2

Answer: N(11) = 32

I could not find the recurrence relation, but I solved it in this way.

The regular expression for this DFA is (01 + 01)((11)* + (010)* + (001)*)* .

Our problem now reduces to basic counting.

Suppose the string is of the form “##&&&&&&&&&”

In how many ways we can make a string of length 11 from the RE (01 + 01)((11)* + (010)* + (001)*)*

From the (10 + 01) part of the RE, we will always have only 2 possible choices for the 2 most significant bits of the string i.e. for “##” .

Now for the remaining 9 least significant bits i.e. for “&&&&&&&&&” we have to dwell into the

((11)* + (010)* + (001)*)*part of our RE.

This part can have only strings whose length is a linear combination of 2 & 3 since it is the kleene closure of strings of length 2 and 3 only.

All possible linear combinations of 2 & 3, which will produce exactly 9 will be,

2 + 2 + 2 + 3, or 3 + 3 + 3.

We have only one choice for length 2(i.e. the string 11) and two choices for length 3(i.e. strings 010 or 001).

For the part 2 + 2 + 2 + 3 => here since the order matters and 3 has two choices, the all possible strings of this type will be à 4C1(to choose a position for the string of length 3) x 2( to choose among 010 and 001) which gives 4 x 2 = 8.

For the part 3 + 3 + 3 => order does not matters here since all strings are of same length, but each string of lenth 3 has two choices so it will give 2^3 = 8.

So Total possible ways of forming strings of length 9 for “&&&&&&&&&” = 8 + 8 = 16.

& Total possible ways of forming strings of length 2 for “##” = 2 (10 or 01).

So all possible ways of forming strings of length 11 for “##&&&&&&&&&” = 2 x 16 = 32.

Answer 3

c) N(11) = 32

Comments

Your answer is useless unless you provide the steps for the solution.