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 joshi_nitish commented Nov 12, 2017 reply Follow Share let D1-> DFA accepting d(s)mod5 = 2 , D2-> DFA accepting d(s)mod7 != 4 making DFA will take time, but total no. of states = 7*5 = 35 no. of final states = no of states in D1$\times$D2, for which atleast one is final in respective D1 or D2. no. of final states= 35 - 4 = 31 1 votes 1 votes Warlock lord commented Nov 12, 2017 reply Follow Share So there's 1 non final state in D2 and 4 non final states in D1. And so 1*4 total non final states, correct? 0 votes 0 votes joshi_nitish commented Nov 12, 2017 reply Follow Share yes, correct. 0 votes 0 votes Anu007 commented Nov 12, 2017 reply Follow Share yes because when both there's 1 non final state in D2 and 4 non final states in D1 combine which is non final otherwise state which contain atleast one state other than these state wil be final 1 votes 1 votes 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.