Question 14297 – Theory-of-Computation
December 19, 2023GATE 2021 CS-Set-2
December 19, 2023Theory-of-Computation
| Question 11 |
Consider the following deterministic finite automaton (DFA).
The number of strings of length 8 accepted by the above automaton is __________.
| 256 |
Question 11 Explanation:
State q3 and q4 are equivalent so they can be merged and states q1 and q2 are also equivalent so they can also be merged hence the min DFA will be
So the DFA accepts all strings of length greater than equal to 3.
For 8 length strings we have 8 positions
_ _ _ _ _ _ _ _
For each position there are two possibilities 0 or 1.
So for 8 positions we have 28 possibilities = 256
Correct Answer: A
Question 11 Explanation:
State q3 and q4 are equivalent so they can be merged and states q1 and q2 are also equivalent so they can also be merged hence the min DFA will be
So the DFA accepts all strings of length greater than equal to 3.
For 8 length strings we have 8 positions
_ _ _ _ _ _ _ _
For each position there are two possibilities 0 or 1.
So for 8 positions we have 28 possibilities = 256