Can every regex be translated into a DFA? Or only a subset of regular expressions?
If so, what is an example of a regular expression that cannot be translated into a DFA?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Every regular expression using only *,+,| (but not, say, backreferences) can be converted into a DFA. This is shown in textbooks on formal languages. Modern regular expressions, as used in actual programming languages, are more powerful than classical ones, and in particular they can recognize non-regular languages, such as the language of squares $w^2$, which is recognized by
A regular expression can only describe a regular language, but it can describe all regular languages. The same is valid for DFA: They can only describe regular languages, but they can describe all regular languages.
So if a regular expression can describe a language, that language is regular, and can be described by a DFA. You can construct such DFA by using Thompson or Glushkov construction (among others) to construct an NFA, and then convert it to a DFA.
If a language is produced by a DFA, it is regular, and can be described by a regular expression. To construct a regular expression from a DFA, have a look at this question.
Note: Outside of theory, people often confuse regular expressions with languages designed for programming, for example PCREs. While they are named "Perl Compatible regular expressions", they are much more powerful than regular expressions or DFA. They can in fact decide some NP-complete problems.