Skip to main content
1 of 3
reinierpost
  • 6k
  • 1
  • 22
  • 38

As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?

No, for several reasons:

  1. Don't say regular languages can be closed under concatenation. What does that mean? Do say the regular languages are closed under concatenation. That means: when you take two regular languages, their concatenation (which is the set of strings formed by concatenating the strings from the first and second language pairwise) is always a regular language. This is true.
  2. Don't confuse regular languages with regular expressions. A regular expression is a way to denote a regular language. The regular language itself is not an expression, it is a set of strings. For instance, $(a^*b)^*$ and $(a\cup b)^*$ are two different regular expressions. They denote the same regular language.
  3. Regular expressions are strings, so the set of regular expressions is a language. What I think you're saying is that this language is closed under concatenation. That is true: the concatenation of two regular expressions is always another regular expression. However, there are infinitely many different regular expressions. Therefore, if you concatenate all of them, you get an infinitely long expression. Infinitely long strings are not considered in the language theory you're studying, so that is not something you can do. Also, concatenating strings is not the same as forming a set of those strings: when I concatenate $aa$, $bb$ and $cc$, in that order, I get $aabbcc$, which is a string; it is not the same as the set of strings $\{aa, bb, cc\}$, which is not a string, but a language (a set of strings).
  4. The regular languages are closed under concatenation, and the language of regular expressions is also closed under concatenation; from this, does it logically follow that the language of regular expressions is regular? No, it doesn't - that reasoning would be an example of affirming the consequent.
reinierpost
  • 6k
  • 1
  • 22
  • 38