Practice Test Series Question

Question

Comments

Understand the language first, this dfa will accept all such strings of length n (n ≥ 3) which has atleast 2 consecutive 1's in last (n-1) positions.I solved using by case method.

---

bro..please check my answer..

---

it’s correct.

Answer 1

This DFA will accept all strings of length n (n ≥ 3) which has minimum of 2 consecutive 1's in

last  (n-1) positions

no.of possibilities in first position=2

no.of acceptable strings with 6 positions =     (total possible strings – no.of rejected strings)

total possible strings =2^6 =64

no.of rejected strings

string which contain only 0’s=1

strings which contain only one 1 = 6         (_0_0_0_0_0_)→ we can place 1 anywhere.==> 6c1

strings which contain two 1’s but not consecutively = 10      (_0_0_0_0_)→ 5c2

strings which contain three 1’s but not consecutively= 4      (_0_0_0_)→ 4c3

now total no.of rejected strings = 1+6+10+4=21

no.of accepted strings of length 7 = 2*(64-21) = 2*43 =86

 

so the answer is 86 strings

Answer 2

State $1$ can accept $1$ character in $2$ ways.

State $2$ can accept $1,2,3,4$ or $5$ characters in one way since allowed length is $7$.

State $3$ can accept $1,3$ or $5$ characters in one way.

State $4$ can accept $0,1,2,3$ or $4$ characters in $2^n$ ways where $n$ is the number of characters accepted.

Counting the possible $7$ character strings:

$0/1 \rightarrow 1 \rightarrow 1 \rightarrow 16$ ways

$0/1 \rightarrow 1 \rightarrow 011 \rightarrow 4$ ways

$0/1 \rightarrow 1 \rightarrow 01011 \rightarrow 1$ way

$0/1 \rightarrow 01 \rightarrow 1 \rightarrow 8$ ways

$0/1 \rightarrow 01 \rightarrow 011 \rightarrow 2$ ways

$0/1 \rightarrow 001 \rightarrow 1 \rightarrow 4$ ways

$0/1 \rightarrow 001 \rightarrow 011 \rightarrow 1$ way

$0/1 \rightarrow 0001 \rightarrow 1 \rightarrow 2$ ways

$0/1 \rightarrow 00001 \rightarrow 1 \rightarrow 1$ way

Total : $2 \times 39 = 78$ strings.

Comments

78 is not the correct answer.

---

Please disprove my answer and reveal which strings I've left behind. Thanks in advance.

---

And the given answers above staes that

The dfa will accept n>2 - that is true

The dfa can only accept strings having 2 consecutive 1s in the last n-1 positions.

It is not clear.

Ok, the problem with the above answer is this point :

Strings which contain three 1's but not consecutively.

It is not 4c3.

Check it and eliminate 8 more.

You will get 78.

Answer 3

Case method is good but this is an alternative