# Is it possible to support .(any symbol) or \d, \w, \W in DFA

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)

• Note that the alphabet is finite, so a line for any symbol isn't a problem. – Karolis Juodelė Nov 28 '13 at 17:18
• 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? – Arsen Mkrtchyan Nov 28 '13 at 18:11
• 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. – Karolis Juodelė Nov 28 '13 at 18:57
• 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 – Arsen Mkrtchyan Nov 28 '13 at 19:59
• 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? – avakar Nov 28 '13 at 20:03

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