0
$\begingroup$

enter image description here This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.

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

$\endgroup$
  • 1
    $\begingroup$ You can do whatever you want, as long as the resulting automaton behaves correctly. $\endgroup$ – Yuval Filmus Dec 16 '18 at 19:59
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Another advantage is that every state has at most two out-transitions, and if it has two they are both epsilons. Given the memory constraints Thompson had to work within, this was a big help. $\endgroup$ – rici Dec 17 '18 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.