DFA that accepts a string such that 2nd symbol from RHS is "a"

Is it possible to design a DFA that accepts a string such that 2nd symbol from RHS is "a"? (Caution - I Know the NDFA for this question & its RHS not LHS.)

19Comments
Pritam Prasun pritam 19 Jul 2016 07:34 pm

What are the input symbols ?

Shubham Thakur imshubhamthakur 19 Jul 2016 07:37 pm

Oops. Sorry. (a,b)

Pritam Prasun pritam 20 Jul 2016 09:03 am

Thanks Himanshu for pointing out the mistake.

Shubham Thakur imshubhamthakur 19 Jul 2016 08:20 pm

How about "aaaab"?

Will this be accepted?

Pritam Prasun pritam 19 Jul 2016 08:28 pm

Nice catch, It needs more thought.

Pritam Prasun pritam 19 Jul 2016 11:52 pm

I have given another try. have a look.

Shubham Thakur imshubhamthakur 20 Jul 2016 05:24 am

The solution given by Himanshu Sir below is the correct one sir. Your machine won't accept "baaa" string. If i am not wrong!!!

Pritam Prasun pritam 20 Jul 2016 09:22 am

Ohhhh a small mistake. Corrected now. Answer credit and thanks to Himanshu.

Himanshu Kaushik gatelectures 20 Jul 2016 12:53 am

is it correct ?

Shubham Thakur imshubhamthakur 20 Jul 2016 05:25 am

Ahaa! Nicely Done. Thank you so much sir. 

Pritam Prasun pritam 20 Jul 2016 07:47 am

Nice, thanks Himanshu.

Shobhit sudsho 20 Jul 2016 01:29 am

i think himanshu sir gave the right answer..

we can easily make the NFA for above and converting it into DFA will lead to the same as above.....

Parth Sharma parthsharmau 4 Aug 2016 03:01 pm

first desgn the nfa then convert it to dfa .

this is the best method to do,instead of directly designing dfa

Parth Sharma parthsharmau 4 Aug 2016 03:02 pm

if u r really good with designing dfa then u can directly design it just keep in mind the purpose of each state

Rahul riishii 6 May 2017 04:27 pm

Hey guys, how about the mDFA which accepts the strings with third last symbol be 'a'. I am really confused. If someone can really help me out with this.

Surajeet Paul surajeetpaul 6 May 2017 05:16 pm

Surajeet Paul surajeetpaul 6 May 2017 05:21 pm

Well the image turned out to be gigantic, but I believe it will help with your query riishii.

Rahul riishii 6 May 2017 06:21 pm

Thanks a lot surjeet. It definitely going to help me. How did you decide the number of states per input?

Surajeet Paul surajeetpaul 6 May 2017 06:52 pm

The easiest way is to create the NFA first and then convert it to DFA. If we directly start creating the DFA, then it would be very much difficult to decide the number of states and number of final states.