The Gateway to Computer Science Excellence

+12 votes

Best answer

0

@Kapil , I have got one doubt here...

Actually when we find cross product we are doing intersection of two languages , right ? In that case the DFA should have to be " Divisible by 4 **AND** Divisible by 5 "

But here here we are getting " Divisible by 4 **OR** divisible by 5 "

Can you pls explain this part a bit.. Inspite of taking cross product we are able to get union of two languages ?

Is my understadning correct about compound automata ?

+1

@Kapil, How long it took you to come up with this solution ( I mean diagram and ans =13 states) ? Because it took me around 1 hr to verify your diagram. After seeing your first diagram ( divisibility by 4), I got that my solution of having 20 states was wrong and thought it must be having 15 or less state.But again, this less than 15 was putting me in trouble. But then finally got that we can merge three states(X0Y0, X1Y0, X2Y0) to one state (X0Y0).

Actually, I had forgotten this cross-product, union rule. :P

By the way, Thanks a lot. : )

Please tell some intuition, if it took you less than 3-4 min ??

Actually, I had forgotten this cross-product, union rule. :P

By the way, Thanks a lot. : )

Please tell some intuition, if it took you less than 3-4 min ??

+1

@vijaycs

Cross Product Explanation is Here . Yeah you need to explain how to got that final diagram a bit, kapil :D

+2

@vijaycs @pC

Cross product of two DFA gives the compound automata.

So, we can go in either direction to find union ( Final state comes whenever X0 comes or Y0 comes ) or intersection ( Final state comes whenever both X0 and Y0 come together )

I took me around 10 minutes , but to make a diagram online, it took much time as I was afraid :)

But, I guess GATE will never attempt to provide such Q.

(They will go for divisible 2 or 3) OR (divisible by 8 or 16 - Here, no need to solve, just logically we have 8 states)

PS: The whole transition table that I made is very horrible, just like my handwriting :P, so its a risk if I upload that here :)

+1

Now, see my horrible diagram : P

Actually, I was making this just by seeing first two DFA( div by 4 and div by 5). without making transition table.

And then, After seeing your diagram, I got that we can merge three states ( states of the first column).

0

@kapil cound u plz explain my doubt on top..

ie Inspite of taking cross product we are able to get union of two languages ?

ie Inspite of taking cross product we are able to get union of two languages ?

+1

@pC only final states changes in case of union and intersection....like if it is divisible by 2 **and **3 then states satisfying both the conditions together will be the final states ...

if it is divisible by 2 **or** 3 then even if one condition is satisfied then that state will be the final one...

0

@Kapil SIR , mod n machine will have n states like wise in your Divisible by 4 Machine shoudn't it have 4 states ?

0

@gokou....we can merge one state here for getting minimal dfa...its nt a rule that if divisble by 4 then there will be 4 states..dont follow such things..even divisible by 8 will have 4 states after minimising the dfa..

0

@pC

Cross product is an approach to get Compound Automata.

But that does not always guarantees intersection. We need to check condition given in the question, i.e OR or AND . If it is OR like in this case, then Union is better to accept {0,4,5,8,10,12,15,16,20............}

and if AND is given, then intersection is better to accept {0,20,40,60,80,100,120,140.........}.

Cross product is an approach to get Compound Automata.

But that does not always guarantees intersection. We need to check condition given in the question, i.e OR or AND . If it is OR like in this case, then Union is better to accept {0,4,5,8,10,12,15,16,20............}

and if AND is given, then intersection is better to accept {0,20,40,60,80,100,120,140.........}.

+1

@sudhso @kapil

I always thought compound atomata always results in Intersection of two languages . Now I got my mistake .

So in the above diagram. If we select final state as X0YO only then the above DFA Will Result in

binary strings divisible by 4 AND 5 , right ?

I always thought compound atomata always results in Intersection of two languages . Now I got my mistake .

So in the above diagram. If we select final state as X0YO only then the above DFA Will Result in

binary strings divisible by 4 AND 5 , right ?

+2

@vijaycs I solved it upto here . It will take less than 10 min . But to draw the diagram will take much time :D And I become confused about **AND** and **OR **condition

0

@Pc,why have u combined M and O??

x0y4 ->one is final and other is non-final

and X2y4 ->both are fnon-final

x0y4 ->one is final and other is non-final

and X2y4 ->both are fnon-final

0

http://www.techtud.com/short-answer-question/binary-string-x-a0a1 ·-·-·-an−1n

Given answer is 5 here

+3 votes

I think, It is 20 states.

If anyone finds optimized DFA with less than 20 states, please let us know.

0 votes

0 votes

It will take 20 states.

using cross product method we can implement AND and OR operations

Divisible by 4 ={q0,q1,q2,q3} q3 final state

Divisible by 5 ={w0,w1,w2,w3,w4} w4 final state

4x5 ={q0w0,q0w1,.....q3w3}

20 states.

To implement OR we need to make final states of all the states which have either q3 or w4 in them.

using cross product method we can implement AND and OR operations

Divisible by 4 ={q0,q1,q2,q3} q3 final state

Divisible by 5 ={w0,w1,w2,w3,w4} w4 final state

4x5 ={q0w0,q0w1,.....q3w3}

20 states.

To implement OR we need to make final states of all the states which have either q3 or w4 in them.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,051 comments

104,678 users