3 votes 3 votes No of states in finite automata whose string length is divisible by 3 or8? Theory of Computation finite-automata theory-of-computation + – Vinil asked Sep 16, 2017 • edited Nov 1, 2017 by LeenSharma Vinil 5.0k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Manu Thakur commented Sep 16, 2017 reply Follow Share 12 should be answer! 1 votes 1 votes Vinil commented Sep 17, 2017 i reshown by Vinil Sep 18, 2017 reply Follow Share @manu00x can you explain how did you get this?? 0 votes 0 votes Manu Thakur commented Sep 17, 2017 reply Follow Share No. of states in finite automata whose string length is divisible by 3 = 3 No of states in finite automata whose string length is divisible by 8 = 4 Compute product automata of above 2 DFA = 4x3 = 12 states. 0 votes 0 votes Vinil commented Sep 17, 2017 reply Follow Share No man... you are wrong ..answer is 24 well i will explain you.., No. of states in finite automata whose string length is divisible by 3 = 3 No. of states in finite automata whose string length is divisible by 8 = 8 Take a cross product of 8*3 which is 24 Why your solution is wrong? No. of states in finite automata whose string length is divisible by 8 = 4 It accepts strings of length:4,12,20....but it is not true BTW no of states in FA whose length is divisible by n is n.. 2 votes 2 votes Manu Thakur commented Sep 17, 2017 reply Follow Share yes you're correct! I missed the word length. ithought string itself is divided by 8. if we are talking about length of string is divided by 8 then 8 states are needed and product automata will have 24 states. 0 votes 0 votes Bhargav D Dave 6 commented Oct 31, 2017 i moved by Bhargav D Dave 6 Nov 1, 2017 reply Follow Share FA of string length divisible by 3 is of 3 state. FA of string length divisible by 8 is of 8 state. In question Given 3 or 8 state (or given) that wise only 8 state require. If Ans then 8 State 0 votes 0 votes Vinil commented Nov 1, 2017 reply Follow Share Take some multiples of 3 and 8 it will not accept all the strings.... 3,6,8,12,15,16....take this string lengths and try it..... 0 votes 0 votes Bhargav D Dave 6 commented Nov 1, 2017 reply Follow Share Check this given Lenth not given any string that wise you get 8.No language given that wise this is also true.You get 0,3,8,6,9,12,15,16,.... 0 votes 0 votes Bhargav D Dave 6 commented Nov 1, 2017 reply Follow Share But check question DFA every every state there should be one transition .In question Ask FA.Not written NFA or DFA if not written then go with NFA it ok. 0 votes 0 votes Vinil commented Nov 1, 2017 reply Follow Share okay in that case, what could be the answer for DFA if it is given in the question? 0 votes 0 votes LeenSharma commented Nov 1, 2017 reply Follow Share Bhargav D Dave 6 in your NFA 6 should be the final state but if we make state 6 as the final state then your NFA will also accept whose string length 14. I think your NFA is not correct. 0 votes 0 votes LeenSharma commented Nov 1, 2017 reply Follow Share Vinil check my answer for DFA. 0 votes 0 votes Sanandan commented Oct 4, 2020 reply Follow Share The answer will be 24 states. 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes $\sum= \left \{ a,b \right \}$ Number of states in deterministic finite automata whose string length is divisible by 3 or 8 = 24 states. LeenSharma answered Nov 1, 2017 • selected Nov 1, 2017 by Vinil LeenSharma comment Share Follow See 1 comment See all 1 1 comment reply Vinil commented Nov 1, 2017 reply Follow Share Exactly....! This is correct answer. 1 votes 1 votes Please log in or register to add a comment.