Need help creating a DFA. It is to accept any string starting with A and ending with D. I've figured the regular expression to be:
A(A+B+C+D)*D
I'm stuck on converting it over to a DFA. Professor said that I have to have it branch into A, B, C, D separate for the states, but after that hint I'm still confused.
I suspect you might be overthinking it a bit. I suggest starting with turning the regular expression into an NFA first, and then modify that NFA to be a DFA.
To help get you started, I'll work out the procedure to get from that to an NFA.
We start with the regex, as you described:
One of the properties of regex to NFA conversion is that of concatenation- when a regex describes a sequence, their states do as well.
So, we do the easy step, and break off the A:
Now, that leaves us with that behemoth on the right. However, we have yet another property of converting a regex to an NFA- closure. Whenever you have a starred expression, that creates a loop. We can take advantage of that, and not even need any new states:
What remains to be done at this point is to just break up the loop, which I won't bother to detail (instead of one looping arrow it'd be four- one for each letter). Now, the task at hand is to convert this NFA to a DFA. I suggest recalling the definition of a DFA, and thinking about how this NFA fails to meet those definitions. Then work out what intermediate nodes you need to add so that this NFA meets those definitions.
Oftentimes when doing these conversions you have a "dead" node- a node that is not a final node, where every input circles back into itself. This is to denote strings that do not meet the desired specifications, such as those that start with a B.