search
Log In
2 votes
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.

in Theory of Computation 600 views
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
questions are correct  i was writing about the answer key.
0
So, which answer part you think is not correct?
0
Question 1

5. Answer should be 13

3*4+1

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

thanks for spotting out error.

please check remaining answers.

1 Answer

0 votes
Q 1

7 answer should be 10.

3*3+1
0
What about remaining questions?

It is very good one for the purpose of GATE.

Related questions

3 votes
2 answers
1
478 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.
asked Jan 15, 2018 in Theory of Computation Sona Barman 478 views
1 vote
0 answers
2
606 views
L = {s ∈ (0 + 1)* d(s)mod5 = 2 or d(s)mod7 != 4} where d(s) is the decimal equivalent of the binary string s. How many states does the above DFA have? How many final states? Please explain your answer.
asked Nov 12, 2017 in Theory of Computation Warlock lord 606 views
2 votes
1 answer
3
262 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
asked Nov 9, 2017 in Theory of Computation rahul sharma 5 262 views
...