3

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).

Alexandre Dias
  • 107
  • 1
  • 6
  • This needs more context. The conversion is trivial once you know the algorithm (and actually even if you don’t), and if you don’t know that, it’s unclear how you want to work with the NFA in the first place, or how you’d understand an answer, for that matter. What’s your level of knowledge? – Konrad Rudolph May 23 '12 at 14:18
  • I'm not going to work directly with the NFA, as what I want to work with is just the DFA. I'm converting regular expressions to DFA (by regex -> NFA -> DFA), but the .* is a case which I think I am handling incorrectly, as when I try to build an automaton with cross transitions, I get state-space blow up (but not when I try to build it without the cross transitions). – Alexandre Dias May 23 '12 at 15:49

1 Answers1

2

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.

Anders Lindahl
  • 41,582
  • 9
  • 89
  • 93