The Gateway to Computer Science Excellence
+3 votes
983 views
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 ------------------
in Theory of Computation by Active (3.8k points) | 983 views
0
ANS----49
+1
yes 49.

Simply $(n+1)a,s\times (n+1)b,s+1$ i.e. 49.
0
how you are getting this formula? please explain
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.
0

1 Answer

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

by Veteran (57k points)
edited by
0
You have missed some transitions, but , even though its right .
+1
Oh sorry all other goes to trap, i forgot in excitement :D
0
why this cannot be 5*7=35 states
+1
very well explained brooo

Related questions

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,645 questions
56,616 answers
195,897 comments
102,365 users