retagged by
9,307 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  ___________

retagged by

6 Answers

Best answer
28 votes
28 votes
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 votes
1 votes
we have 8 edges in total. each edge has only 2 options either 0 or 1 so

2^8=256.
Answer:

Related questions

23 votes
23 votes
3 answers
2
13 votes
13 votes
3 answers
4
Arjun asked Feb 18, 2021
4,753 views
If $x$ and $y$ are two decimal digits and $(0.1101)_2 = (0.8xy5)_{10}$, the decimal value of $x+y$ is ___________