1
$\begingroup$

Is it possible to build DFA that support \d, \w, .(any symbol)? I understand that we can add each symbol from [0-9] as a separate edge for some of the symbols, but what about the others? for example .(any symbol)? or \S (not white space)?

In other words, can we build equivalent DFA for this NFA

(1) ---a----> (2)
 |
 | 
 .(any symbol)
 |
 \/
 (3)
$\endgroup$
  • 1
    $\begingroup$ Note that the alphabet is finite, so a line for any symbol isn't a problem. $\endgroup$ – Karolis Juodelė Nov 28 '13 at 17:18
  • $\begingroup$ I understand that, but I think creating all possible two byte char symbols for ., or not an space(/S) symbol may not be good idea... I am thinking to keep ranges, and split it while converting to DFA. Do you think this will work? $\endgroup$ – Arsen Mkrtchyan Nov 28 '13 at 18:11
  • 1
    $\begingroup$ DFA is a theoretical construct - a way to write down what regular language means. You're putting a bit too many practical considerations into this. $\endgroup$ – Karolis Juodelė Nov 28 '13 at 18:57
  • $\begingroup$ You are right Karolis, I am just trying to implement DFA, that supports most of the modern regular concepts, expect backtracking(supporting backtracking for DFA is NP problem). I think range is pritty good idea, will give a try, thanks for hint $\endgroup$ – Arsen Mkrtchyan Nov 28 '13 at 19:59
  • $\begingroup$ Do you mean that deciding whether a regular expression with backtracking represents a regular language is NP-complete? Could you point me to a reference? $\endgroup$ – avakar Nov 28 '13 at 20:03
4
$\begingroup$

The symbols you mention represent sets of characters. For example, \d represents the set $\{0,1,2,3,4,5,6,7,8,9\}$. Whenever you want to place \d, replace it with 10 parallel edges labeled with all digits instead. The same works for your other examples, as long as each symbol represents one character. (Otherwise you would get a "generalized NFA".)

$\endgroup$
  • $\begingroup$ so for ., I should put all possible unicode chars? or for \S all symbols except space? I think it may make sense to keep intervals as ranges and split it on NFA->DFA convertion $\endgroup$ – Arsen Mkrtchyan Nov 28 '13 at 18:05
  • $\begingroup$ @ArsenMkrtchyan, exactly. Sure, it will be huge, and the diagram will take a block or so of real estate. But it is finite, so no sweat in theory. In practice, you'll want to take shortcuts like only mentioning "relevant" characters/edges, or even resort to some form "if none of the above, do this" when representing the automaton as a transition table in a program. Search for "transition table compression", the dragon book details one technique. $\endgroup$ – vonbrand Feb 23 at 19:40

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.