0
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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^*\}$.

$\endgroup$
  • $\begingroup$ @reinierpost Ah, yes. That’s probably the point of the question! $\endgroup$ – David Richerby Mar 8 '18 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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