# Important Question for number of states in DFA

600 views

Q1> How many numbers of states are there in minimal DFA for the following languages formed over input = {a, b}

1. a div by 2 and b not div by 3.

2. a not div by 3 and b div by 4.

3. a div by 2 and b at least 2.

4. a at least 2 or b at least 3.

5. a exactly 2 and b at least 3.

6. a exactly 3 and b at most 3

7. a exactly 2 or b at least 2.

8. a exactly 4 and b at least 2.

Q2> How many numbers of states are there in minimal DFA for the following languages formed over input = {a, b, c}

1. a div by 2 and b not div by 3 and c div by 6.

2. a not div by 3 and b div by 4 and c at least 3.

3. a div by 2 and b at least 2 and c at most 4.

4. a at least 2 or b at least 3 or c at least 4.

5. a exactly 2 and b at least 3 and c at most 2.

6. a exactly 3 and b at most 3 and c exactly 3.

7. a exactly 2 or b at least 2 and c at most 5.

8. a exactly 4 and b at least 2 or c exactly 4.

How to calculate the number of states in such question.

It will be good if someone tells how to draw the DFA of such question.

1
why restrict to 2,3 and 4? something like 8,9 and 10 will be better :)
0
Sure Sir, but these figures are small.
1
yes, good exercise to those giving GATE :)
0
@Arjun sir, Please verify my answers whether they are wrong or ryt:-

Answer 1>    {6, 12, 6, 12, 12, 17, 7 ,16}

Answer 2>    {36, 36, 19, 100, 37, 65, 55, 61}

ryt?
0

this is not right key . Because in case of exactly length n  we can not direct multiply because we make only on halt state not more than one which are product of cross product method (can not give always optimal DFA).

https://gateoverflow.in/70753/the-least-number-of-states-in-dfa

0
Which question's part you think is not correct. Please specify the part of that question.
0
0
So, which answer part you think is not correct?
0
Question 1

3*4+1

Extra 1 for half state of exactly 2
0
Yeah that should be 13.

thanks for spotting out error.

Q 1

3*3+1
0

It is very good one for the purpose of GATE.

## Related questions

1
477 views
Self doubt: Is there any method to calculate number of states in dfa e.g."x mod y" type of question without drawing dfa? Because in Gate time is vital factor.
1 vote