ANS----49

The Gateway to Computer Science Excellence

+3 votes

L= set of all strings of a's and b's with exactly 5 a's and 7 b's

if DFA M accepts L. The least number of states in M is ------------------

if DFA M accepts L. The least number of states in M is ------------------

0

It is kind of bruite force.

Try for minimum state Dfa in set of all strings of a's and b's with exactly 2 a's and 3 b's =13

Try for minimum state Dfa in set of all strings of a's and b's with exactly 3 a's and 4 b's=21

Like this you can formulate.

Try for minimum state Dfa in set of all strings of a's and b's with exactly 2 a's and 3 b's =13

Try for minimum state Dfa in set of all strings of a's and b's with exactly 3 a's and 4 b's=21

Like this you can formulate.

0

with respect to this sir can you please answer https://gateoverflow.in/70749/number-of-states-in-minimal-finite-automata#a70759

+7 votes

Best answer

It is a 5 by 7 grid with one trap state. Language is consists of 12 length strings and to get one such string, we can choose any 5 spot for a's and rest 7 spot will be for b's.

Like the following has exactly 2 a's and 2 b's

As we need ( 3 * 3 + 1 ) = 10 states for 2 a's and 2 b's.

Similarly, For 5 a's and 7 b's, we need ( 6 * 8 + 1) = 49 states.

This problem resembles to a good combinatorial problem of finding no of paths in such a graph from start node to end node.

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

50,645 questions

56,616 answers

195,897 comments

102,365 users