The Gateway to Computer Science Excellence
+2 votes
489 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 by Boss (18.2k points) | 489 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
by Active (2.4k points)
0
What about remaining questions?

It is very good one for the purpose of GATE.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,519 comments
100,950 users