Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Consider a DFA accepting all strings over {a,... Start Learning for Free
Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?

  • a) 
    4
  • b) 
    2
  • c) 
    6
  • d) 
    8
Correct answer is option 'C'. Can you explain this answer?
Verified Answer
Consider a DFA accepting all strings over {a, b} where the number of a...
The above question is an example of product automata. If we have two cases for which we can have separate DFA’s we can merge the two by product automata. The resulting DFA has number of states equal to the product of the states of the separate DFA’s. Here DFA for accepting all strings over {a, b} where the number of a’s mod 3 = 2 would have 3 states. ( number of a’s mod 3 would give remainder either 0, 1, 2 so 3 states to depict each). Similarly DFA accepting all strings over {a, b} where the number of b’s are odd ( number of b’s mod 2 = 0) would have 2 states. Hence resulting DFA for both the conditions would have 2*3 = 6 states.
View all questions of this test
Most Upvoted Answer
Consider a DFA accepting all strings over {a, b} where the number of a...
Explanation:

To construct a DFA that accepts all strings over {a, b} where the number of a's mod 3 = 2 and the number of b's are odd, we need to consider the possible combinations of a's mod 3 and odd b's.

States:
Let's consider the possible combinations of a's mod 3:
- If the number of a's mod 3 = 0, we can represent it with state A.
- If the number of a's mod 3 = 1, we can represent it with state B.
- If the number of a's mod 3 = 2, we can represent it with state C.

Transitions:
From each state, we need to consider the possible transitions based on the next input symbol:
1. If the next input symbol is 'a', the number of a's mod 3 will increment by 1. So, the transitions will be:
- From state A, if the next input symbol is 'a', we will transition to state B.
- From state B, if the next input symbol is 'a', we will transition to state C.
- From state C, if the next input symbol is 'a', we will transition back to state A.
2. If the next input symbol is 'b', the number of b's will increment by 1. So, the transitions will be:
- From state A, if the next input symbol is 'b', we will stay in state A.
- From state B, if the next input symbol is 'b', we will transition to state B.
- From state C, if the next input symbol is 'b', we will stay in state C.

Accepting States:
We need to define the accepting states based on the conditions given:
- The number of a's mod 3 = 2 (state C).
- The number of b's is odd.

DFA Diagram:
Based on the above transitions and accepting states, we can construct the DFA diagram as follows:

```
a
------------
| |
v |
---> A ---> B --|
| ^ | |
| | b |
| | | |
-- C < />
```

Minimum Number of States:
To find the minimum number of states required for this DFA, we can use the concept of Myhill-Nerode equivalence. In this case, there are 3 distinct combinations of a's mod 3 (0, 1, 2) and 2 distinct possibilities for the number of b's (odd, even). So, the total number of distinct combinations is 3 * 2 = 6. Therefore, the minimum number of states required for this DFA is 6.

Hence, the correct answer is option C) 6.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer?
Question Description
Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer?.
Solutions for Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer?, a detailed solution for Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? has been provided alongside types of Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Consider a DFA accepting all strings over {a, b} where the number of a’s mod 3 = 2 and number of b’s are odd. What is the minimum number of states of such DFA ?a)4b)2c)6d)8Correct answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev