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
I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent regular language? Or is the set of regular languages a subset of regular expressions?
If this is not the case, is there a good example of a regular expression that does not have an equivalent regular language?
It's a standard part of any automata theory course that regular expressions, deterministic finite automata and nondeterministic automata all define the same class of languages. Any individual exposition will take one of those three things as defining the class of regular languages.
So, yes, all regular expressions define regular languages, and every regular language is the set of strings that match some regular expression.
At least, the above is true for regular expressions as used in computer science. Perhaps the confusion in the question arises from the fact that many computer systems such as text editors, programming languages/libraries and command shells have pattern-matching features that they call "regular expressions" but which are more powerful than CS regular expressions. @reinierpost provides the example that egrep '^(.*)\1 matches the non-regular language $\{ww\mid w\in\Sigma^*\}$.
