The Gateway to Computer Science Excellence
+1 vote
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.
in Theory of Computation by Active (3.3k points) | 227 views

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

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?
yes, correct.

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


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.

@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.

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

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,542 answers
101,534 users