Converting dot-star regular expression into NFA

1.3k views Asked by At

I'm converting a given set of regular expressions into a single NFA, but I'm having some issues. How should I convert a regular expression such as "ab.*c" (representing matching an 'a', a 'b', any number of characters, and then a 'c')?

My final goal is to convert the single NFA into a DFA (and I'm using the subset construction algorithm for that).

1

There are 1 answers

0
Anders Lindahl On BEST ANSWER

A .* in a regular expression corresponds to a looping state in the NFA for every letter of its alphabet.

That state will also have transition for c to the acceptance state.

It is perfectly ok to have c both in the loop transition and the acceptance transition - that's why it is nondeterministic.