1 votes 1 votes L = {s ∈ (0 + 1)* d(s)mod5 = 2 or d(s)mod7 != 4} where d(s) is the decimal equivalent of the binary string s. How many states does the above DFA have? How many final states? Please explain your answer. Theory of Computation theory-of-computation finite-automata number-of-states + – Warlock lord asked Nov 12, 2017 Warlock lord 2.2k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Rupendra Choudhary commented Nov 12, 2017 reply Follow Share L1 = {d(s)mod a =x} L2={d(s)mod b =y} L=L1∩L2 or L1∪L2 L will contain a*b number of states DFA can easily be drawn like tale matrix of size 5*7 , where each row will corresponds to d mod5=0 , d mod5=1 ,d mod5=2 , d mod 5=3 , d mod5=4 and every column will like wise d mod7=0 , d mod 7 =1,,,,,.........d mod 7 =6 Now you can easily check with this 5*7 matrix , which state will correspond to final state. for such type of question , there is no need to make exact transitions , just we have to know , which state will correspond to what o/p. 0 votes 0 votes Warlock lord commented Nov 13, 2017 reply Follow Share @Rupendra Let's take a small example : two dfa's (DFA1 and DFA2) of which the first one generates 'abb' and the other one produces 'baa'. Both DFA's need minimum four states each. If we were to find DFA1 U DFA2 , it would only need 7 states (Tested after drawing the state). But if we take cross product like you mentioned it would need 16 states. Please tell me my flaw in understanding this concept. 0 votes 0 votes Rupendra Choudhary commented Nov 13, 2017 reply Follow Share dear warlock , what i told you , is specific for your asked question only, don't misinterpret it with some general formula , if pattern of language is like L1 = {d(s)mod a =x} L2={d(s)mod b =y} then only apply , what i told. what you're doing is case of M1*M2, # concatenation 1 votes 1 votes Please log in or register to add a comment.