-1
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ This is so general reference. Literally every resource talking on regular languages will hand you the answer. What have you read? $\endgroup$
    – Raphael
    Dec 13 '16 at 7:30
  • $\begingroup$ That said, if you are talking regexp, not regular expressions, answers are different but still easy. Consider (.*)\1, for instance, which isn't even context-free. $\endgroup$
    – Raphael
    Dec 13 '16 at 7:30
  • $\begingroup$ Related question, with links to more. $\endgroup$
    – Raphael
    Dec 13 '16 at 7:31
3
$\begingroup$

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 (.*)\1.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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