166 views
How many  states in dfa of X= { (a+b)*  where no of a is divisible by 4 and 8}

reopened | 166 views
0
I think 8 states.

bcz divisible by 8 is divisible by 4 , but viceversa is not true
0

4 states required for divisable by 4 (4,8,12,16.....)

8 states requied for divisble by 8(8,16,24,32,....)

So,for divisable by 4 and 8 (8,16,24....) ,No.of states-8
0
but for counting 8 zeros  9 states are required?
0
@Deepak Kumar  there there are many common states between multiple of 4 an 8
0
It should be 8 states.
0
It must be 8. Each state will represent remainder 0 to 7.
0
got it
0

ya ,I correct it now saw my answer...

and for counting n's 0 ,no.of states n+1

As Example- +1 vote If question is no. of state divisible by 4 or 8 then answer = 4states

by Boss (10.5k points)
+1
yeah bro got it thanks
0
After forth a should be one more final state to accept divisible 4 a's
0

@thepeeyoosh question is no. of a divisible by 4 and 8 this condition to hold simultaneouly

if aaaa is accepted then  these are divisible by 4 but not 8

+1
Ohh! Sorry got it .

Thank you