The Question is : Do i have to convert the entire given DFA to an ε-NFA(which will result in more states),add the keywords(with ε transitions too)and then convert back to a DFA or i just have to add the keywords so that the DFA becomes an NFA and then convert back to a DFA
There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's necessary to do so, and it's not because it's efficient to do so.
Thompson's construction has the following advantages:
- It's recursive on the structure of the regular expression.
- It's easy to convince yourself that the construction is correct.
- It's straightforward to incorporate certain extensions (e.g. the LEX lookahead operator "/").
Real-world implementations of regular expressions, even if they are based on Thompson's construction, typically optimise a dozen or so common base cases (e.g. Kleene closure of a character set;
[a-zA-Z0-9_]* expands to something much bigger than it needs to be), saving Thompson's rules for higher levels.