3 votes 3 votes How many states in dfa of X= { (a+b)* where no of a is divisible by 4 and 8} Theory of Computation theory-of-computation finite-automata + – raviyogi asked Jan 9, 2018 • reopened Jan 21, 2018 by raviyogi raviyogi 759 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Ashwin Kulkarni commented Jan 9, 2018 reply Follow Share I think 8 states. bcz divisible by 8 is divisible by 4 , but viceversa is not true 0 votes 0 votes Deepak Kumar 12 commented Jan 9, 2018 i edited by Deepak Kumar 12 Jan 9, 2018 reply Follow Share 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 votes 0 votes raviyogi commented Jan 9, 2018 reply Follow Share but for counting 8 zeros 9 states are required? 0 votes 0 votes raviyogi commented Jan 9, 2018 reply Follow Share @Deepak Kumar there there are many common states between multiple of 4 an 8 0 votes 0 votes thepeeyoosh commented Jan 9, 2018 reply Follow Share It should be 8 states. 0 votes 0 votes gauravkc commented Jan 9, 2018 i edited by gauravkc Jan 9, 2018 reply Follow Share It must be 8. Each state will represent remainder 0 to 7. 0 votes 0 votes raviyogi commented Jan 9, 2018 reply Follow Share got it 0 votes 0 votes Deepak Kumar 12 commented Jan 9, 2018 reply Follow Share ya ,I correct it now saw my answer... and for counting n's 0 ,no.of states n+1 As Example- 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes If question is no. of state divisible by 4 or 8 then answer = 4states sumit goyal 1 answered Jan 9, 2018 sumit goyal 1 comment Share Follow See all 4 Comments See all 4 4 Comments reply raviyogi commented Jan 9, 2018 reply Follow Share yeah bro got it thanks 1 votes 1 votes thepeeyoosh commented Jan 9, 2018 reply Follow Share After forth a should be one more final state to accept divisible 4 a's 0 votes 0 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share @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 0 votes 0 votes thepeeyoosh commented Jan 9, 2018 reply Follow Share Ohh! Sorry got it . Thank you 1 votes 1 votes Please log in or register to add a comment.