Question

Find dfa's that accept the following languages L (aa* + aba*b*).

Answer 1

Answer:

That depends upon what you mean by the + symbol. Normally, it represents “positive closure”, one or more. However, the way you have written it, suggests it means “or”.

In either case, you build such a DFA step-by-step. I would use the following algorithm, it is based loosely on Glushkov’s algorithm, how one builds an LR(0) machine, and how one builds an LL machine. This is roughly the algorithm we use in Yacc++ (reduced to handle this case).

First, make dotted items. Dotted items are versions of your regex with a dot symbol (doesn’t have to be a dot, but that is traditional) before each symbol (character), in your alphabet. You also add a dotted item at the end of the rule for “accept”.