The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.1k views

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

  1. $15$ states
  2. $11$ states
  3. $10$ states
  4. $9$ states
asked in Theory of Computation by Veteran (59.5k points)
edited by | 1.1k views
+1

This Might help ...

1 Answer

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

answered by Veteran (355k points)
edited by
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?
0
for divisble by 2 and 4 , cross product give 8 but it can be made by only 4 states ..(lcm of 2,4)
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?
+1
its lcm only ...24 , not 96 , thats why i wrote lcm(2,4 )
+1

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

https://gateoverflow.in/723/gate2001-2-5

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

@sid1221 

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.



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

38,039 questions
45,533 answers
131,816 comments
48,849 users