1,392 views

3 Answers

Best answer
2 votes
2 votes

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.

selected by
1 votes
1 votes
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.
0 votes
0 votes
c) N(11) = 32

Related questions

3 votes
3 votes
1 answer
1
Vinil asked Sep 16, 2017
4,950 views
No of states in finite automata whose string length is divisible by 3 or8?
0 votes
0 votes
2 answers
2
rohankrishan asked Jun 29, 2022
230 views
Example: 11110100000111 should be accepted. There are 6 zeros. 6 is divisble by 2 and 3. This machine required at least six states.
14 votes
14 votes
5 answers
3
Vikrant Singh asked Feb 1, 2015
4,292 views
No. of states in the minimal finite automata which accepts the binary strings whose equivalent is divisible by 32 is ________?A. 5B. 6C 31D 32
1 votes
1 votes
1 answer
4