26 votes 26 votes The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has $2$ states $3$ states $4$ states $5$ states Theory of Computation gatecse-2002 theory-of-computation normal finite-automata minimal-state-automata + – Kathleen asked Sep 15, 2014 edited Feb 12, 2018 by kenzou Kathleen 7.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply pankaj_vir commented Mar 23, 2018 reply Follow Share Modulo 3 gives remainder as ( 0, 1, 2 ) 3 states needed 0 votes 0 votes Please log in or register to add a comment.
Best answer 30 votes 30 votes Correct Option: B It is $3$ states as we need a state each for length mod $3 = 0, 1$ and $2$. priya023 answered Feb 4, 2015 edited May 6, 2021 by soujanyareddy13 priya023 comment Share Follow See all 7 Comments See all 7 7 Comments reply Sid Mukherj commented Oct 14, 2017 reply Follow Share Can anybody please explain why 2 states is wrong answer ? Please find the below diagram in reference to my query. 0 votes 0 votes smsubham commented Oct 17, 2017 i edited by smsubham Oct 17, 2017 reply Follow Share @Sid Try string "1". It will be accepted by your machine though length of string isn't divisible by 3. General formula: a (mod n) then we will have n states in minimal DFA, which is unique. If DFA isn't minimal we may have more number of states. 0 votes 0 votes Sid Mukherj commented Oct 18, 2017 reply Follow Share Yes now I understand the point. My answer would be applicable for length as odd number rather than as divisible by 3. 0 votes 0 votes smsubham commented Oct 19, 2017 reply Follow Share @Sid Yes for the odd number it is applicable with q0 as starting state. 0 votes 0 votes Subhan De 1 commented Sep 14, 2018 i edited by Subhan De 1 Sep 14, 2018 reply Follow Share In the question it is saying {x | length of the x is divisible by 3} not the x itself is divisible by 3 . So, the answer should be B. 3 states but diagram would be 3 votes 3 votes Adarsh Pandey commented Sep 19, 2018 reply Follow Share what about length 0,why initial state is final state? 0 votes 0 votes Satbir commented Jul 24, 2019 reply Follow Share because 0 mod 3 =0 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes Option B is Correct Devwritt answered Mar 30, 2018 Devwritt comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Correct option is B. Mostafize Mondal answered Oct 26, 2018 Mostafize Mondal comment Share Follow See 1 comment See all 1 1 comment reply ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Oct 24, 2023 reply Follow Share but your thought on this is not correct question is saying for length of the string must be divisible on by 3 . 0 votes 0 votes Please log in or register to add a comment.