Virtual GATE @virtualgate added a Question 29 Jan 2015 Virtual GATE 2015 - Question 45 Given Answer: 4 Discuss the solution. 14Comments thumbs up down up1 liked Parimal Andhalkar @parimal_andhalkar 29 Jan 2015 01:00 am plz explain /// up0 like Log in or register to post comments vishal @vishal92 29 Jan 2015 01:18 pm i know only that nth symbol frm right has m^n state here m=no of i/p symbl n =Ith symbol from right so 3^2=9 up0 like Log in or register to post comments Anuj @anujssj5 29 Jan 2015 10:54 pm Can somebody explain it diagramaticaly? up0 like Log in or register to post comments Lakshmi Bansal @lakshmibansal 4 Feb 2015 07:15 pm i m getting this answer please tell me the mistake up0 like Log in or register to post comments kn nk @knkn 2 Feb 2016 09:49 pm It doesn't have any mistake but the two final states can be merged into one. Thus minimum number of states would be 3 instead of 4. up0 like Log in or register to post comments A Arul S @innovwelt 4 Feb 2015 08:29 pm @lakshmibanshal: looks good. I do not find any mistake in the DFA. up0 like Log in or register to post comments Lakshmi Bansal @lakshmibansal 4 Feb 2015 08:40 pm then why the answer is 9? up0 like Log in or register to post comments S shubham @shubhu1 26 Jun 2018 08:15 am Yup....Correct answer is 9!! @lakshmibansal. first you should draw NFA for this question.and convert that NFA to DFA.NFA will contain 4 states...and after converting that NFA to equivalent DFA it will have 9 state. up0 like Log in or register to post comments S shubham @shubhu1 26 Jun 2018 08:35 am http://www.techtud.com/sites/default/files/public/user_files/tud46326/me... up0 like Log in or register to post comments S shubham @shubhu1 26 Jun 2018 08:37 am up0 like Log in or register to post comments Ashish Kumar Goyal @dashish 27 Aug 2018 04:38 pm No need to keep states A and B separate. Why don't you try keeping them together... also, your conversion to DFA is wrong. Pls check it once. up0 like Log in or register to post comments H Harsh @harshitgoel 26 Aug 2018 02:40 am i am getting answer is 4 up0 like Log in or register to post comments A Adeema jain @adeema 10 Oct 2018 04:57 pm There will be 4 states in minimized dfa. up0 like Log in or register to post comments Ashish Kumar Goyal @dashish 11 Oct 2018 02:29 pm up0 like Log in or register to post comments

plz explain ///

i know only that nth symbol frm right has m^n state

here m=no of i/p symbl

n =Ith symbol from right

so 3^2=9

Can somebody explain it diagramaticaly?

i m getting this answer

please tell me the mistake

It doesn't have any mistake but the two final states can be merged into one. Thus minimum number of states would be 3 instead of 4.

@lakshmibanshal: looks good. I do not find any mistake in the DFA.

then why the answer is 9?

also, your conversion to DFA is wrong. Pls check it once.