**This Might help ...**

**
**

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

Your identity must be verified before you can ask a question. Please wait if already uploaded identity proof or upload your proof here
Close

+15 votes

A minimum state deterministic finite automaton accepting the language

$L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has

- $15$ states
- $11$ states
- $10$ states
- $9$ states

+21 votes

Best answer

Answer will be (**A**) $15$ states.

We need a separate state for #$0 = 0, 1, 2$ and #$1 = 0, 1, 2, 3, 4$ giving total minimum number of states $= 3 * 5 = 15. $

This is a direct consequence of Myhill-Nerode theorem.

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

0

@Arjun Sir, So this is a cross product between 2 DFAs "number of 0 ...." and "number of 1 ...."

My question is..... Do we always get minimal DFA after cross product or we need to check if it can be minimized?

My question is..... Do we always get minimal DFA after cross product or we need to check if it can be minimized?

0

Yes,

-> divisible by 2 and 4 is clear and direct.. 4 is direct multiple.

-> divisible by 3 and 4 is direct.... they are relatively prime to each other

But if question will be like divisible by 12 and 8... Whats the answer here?

Do we need to check if it can be minimized or answer is 12*8?

-> divisible by 2 and 4 is clear and direct.. 4 is direct multiple.

-> divisible by 3 and 4 is direct.... they are relatively prime to each other

But if question will be like divisible by 12 and 8... Whats the answer here?

Do we need to check if it can be minimized or answer is 12*8?

0

@sid1221 if,L={w∣w∈{0,1}^{∗}, number of 0s and 1s in w are **divisible by 2 and 4**, respectively} Can you show how can we create the finite state machine accepting it in 4 states as per the method of lcm(2,4) ??

0

its lcm only ...24 , not 96 , thats why i wrote lcm(2,4 )

but careful its length of w , which is divsible by x and y number ... for symbol its not case

Can you please explain it in more detail. I am not getting what you are telling about the symbol.

0

I don't think this lcm is going to work here. question is asking about number of a's divisible by 3 and number of b's divisible by 5. here number of states according to myhill nerode will be number of remainders for 3 * number of remainders of 5. Similarly if it would have been 2,4 it has to be 8. for 2 {0,1} * for 4 {0,1,2,3} and our final state is {0,0} and total states = 8.

@Ahwan @Arjun sir please help if approach is correct.

@Ahwan @Arjun sir please help if approach is correct.

+1

for divisble by 2 and 4 , cross product give 8 but it can be made by only 4 states ..(lcm of 2,4)

States in DFA for counting a,b is nothing but all possible combinations of their remainders. I don't think LCM has to do anything with this.

@Shaik Masthan @Ayush Upadhyaya plz correct if wrong.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,109 questions

53,221 answers

184,629 comments

70,463 users