Virtual GATE 2015 - Question 45

Given Answer: 4
Discuss the solution.

Parimal Andhalkar @parimal_andhalkar
29 Jan 2015 01:00 am

plz explain  ///

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


Anuj @anujssj5
29 Jan 2015 10:54 pm

Can somebody explain it diagramaticaly?

Lakshmi Bansal @lakshmibansal
4 Feb 2015 07:15 pm

i m getting this answer
please tell me the mistake 

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.

Arul S @innovwelt
4 Feb 2015 08:29 pm

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

Lakshmi Bansal @lakshmibansal
4 Feb 2015 08:40 pm

then why the answer is 9?

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.
shubham @shubhu1
26 Jun 2018 08:37 am

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.
Harsh @harshitgoel
26 Aug 2018 02:40 am
i am getting answer is 4
Adeema jain @adeema
10 Oct 2018 04:57 pm
There will be 4 states in minimized dfa.
Ashish Kumar Goyal @dashish
11 Oct 2018 02:29 pm