Steps to draw a DFA (or NFA) from a simple statement?
I am given a simple statement: Construct a DFA over alphabet {0, 1} that accepts all the strings that end in 101?
My question is that what will be the steps to design it? Or design an NFA, because then I know the clear steps yo convert an NFA to a DFA, so I will then convert the NFA to the DFA.
Note:- It is just a minor course for me, so I have never studied anything like regular expressions, or any algorithms probably used to construct DFA's.
Answer
If you want more of an explanation on how I derived this, I'd be happy to explain, but for now I just drew the DFA and explained each state.
Sorry about the screenshot...I didn't know how to convert it straight to an image.
On input 0 at state 0, it loops back to itself. On 1, it prepares itself to end because it could possibly be '101'.
q1 loops to itself on input 1 because it's still preparing to end on '101'. Input '0' on q1 means it is preparing for input '10', so it goes to q2.
Input '0' on q2 breaks the whole cycle and goes back to q0. Input '1' results in moving to q3, the accepting state.
Any input on q3 results in going back to whatever point in the cycle the input corresponds with.
That is, on '1' it goes back to q1, or the state where the first '1' was encountered in '101', preparing to end.
On '0', it goes to q2 because in order to get to q3, there must have been an input of '1' from q2, so no matter what, the last two input symbols are '10' now.