The Gateway to Computer Science Excellence
+3 votes
166 views
How many  states in dfa of X= { (a+b)*  where no of a is divisible by 4 and 8}
in Theory of Computation by Active (2.5k points)
reopened by | 166 views
0
I think 8 states.

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

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 Answer

+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
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,737 questions
57,366 answers
198,496 comments
105,265 users