in Theory of Computation retagged by
9,286 views
20 votes
20 votes

Consider the following deterministic finite automaton $\text{(DFA)}$

The number of strings of length $8$ accepted by the above automaton is  ___________

in Theory of Computation retagged by
by
9.3k views

2 Comments

Any string starting with 00,11,10,01 followed by either 0 or 1 is accepted.So the minimum length of the string which is accepted by this DFA is 3 and Regular Expression is of the form $(0+1)^{^{3}}$$(0+1)^{^{*}}$, so every string of length >=3 is accepted ,hence number of 8 length string that can be formed using {0,1} is $2^{^{8}}$ i.e 256, so all the string will be accepted i.e 256 string will be accepted.
4
4
_ _ _ _ _ _ _ _    Total length is 8.

 

(start , 0)

0 0 0 _ _ _ _ _

0 0 1 _ _ _ _ _

0 1 0 _ _ _ _ _

0 1 1 _ _ _ _ _

 

(start , 1)

1 1 0 _ _ _ _ _

1 1 1 _ _ _ _ _

1 0 0 _ _ _ _ _

1 0 1 _ _ _ _ _

 

We can see , there are 2^3 = 8 paths to reach Accept state.

So total 8 Length strings can reach Accept State  = 2^3 * 2^5 = 2^8 = 256.
6
6

6 Answers

28 votes
28 votes
Best answer
The answer is $256$.

We can reach the final state with all possible strings of length three on set $\{0,1\}.$

So there are $8$ ways to reach the final state and we will have a five-length string remaining where we have two options – either $0$ or $1,$ for each of the $5$ positions.

So, total number of strings accepted will be $8 \times 2^5 = 2^8 = 256.$
selected by
3 votes
3 votes
The answer given below is correct as well as fine. I will try to provide an idea that will work in more general situations as well. The idea is as follows. Note that above graph is DAG (directed acyclic graph). So there will be a node in which there is no incoming edge (don’t confuse yourself with start state arrow). The answer in the above given graph is start state. Remove it from the graph and keep a number of ways as well as length to every other vertex in the resultant graph. Now you again repeat the previous step until you are left with only two or one vertices. The goal of this paragraph is to explain you from where number 8 (as in the anser below) is coming to the picture.

In the above question you need to find the paths of length 8 from start state to the final state. If you do the steps I have described in the above paragraph. You will left with only accept state. There will be 8  paths of length 3 from the start to the final state. Later part of answer is same as mentioned in the answer below.
2 votes
2 votes

Total there will be 256 strings accepted by this DFA. The prefixes will be

00--------

01--------

10--------

11--------

1 vote
1 vote
we have 8 edges in total. each edge has only 2 options either 0 or 1 so

2^8=256.
Answer:

Related questions