The Gateway to Computer Science Excellence

+2 votes

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.**

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?

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,700 answers

199,397 comments

107,476 users