# Can every single regular expression be translated into deterministic finite automata? [closed]

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?

• This is so general reference. Literally every resource talking on regular languages will hand you the answer. What have you read?
– Raphael
Dec 13 '16 at 7:30
• 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.
– Raphael
Dec 13 '16 at 7:30
• Related question, with links to more.
– Raphael
Dec 13 '16 at 7:31

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.