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?
3
-
$\begingroup$ Welcome! I edited your title, since it didn't seem obviously related to your question. $\endgroup$– David RicherbyCommented Nov 16, 2015 at 11:45
-
$\begingroup$ @DavidRicherby Hi. Actually, that is part of my question. I am given a question about the set of all regular expressions and where they are classified under. The solutions say 'Context-Free'. $\endgroup$– Helena NgCommented Nov 16, 2015 at 14:20
-
1$\begingroup$ I can't tell what your question is. The title is an entirely different question than the body. Can you please edit the question to clarify what you are asking? Perhaps you can give an example to clarify what you have in mind? ("The set of all..." is quite different from "The concatenation of all...".) And what are your thoughts? $\endgroup$– D.W. ♦Commented Nov 17, 2015 at 0:48
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"
The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^*b(a+c)^*$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).
$\begingroup$
$\endgroup$
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:
- 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.
- 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.
- 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).
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.
The language of regular expressions is not regular. This is due to the fact that brackets must always match up, which is something regular expressions cannot express.
answered Nov 18, 2015 at 8:43
$\begingroup$
$\endgroup$
3
The regular languages are closed under finitely many applications of choice, star, concatenation. If you allowed infinitely many applications, every language would be regular since every language $L$ satisfies $L = \bigcup_{w \in L} \{w\}$. I'm not sure how context-free languages come into this.
Also, what is the concatenation of all regular languages over a given alphabet $\Sigma$? If we do concatenate $\emptyset$, then we end up with $\emptyset$. If we exclude that from the concatenation, then the length of the words in the concatenation is monotonically increasing in the number of languages you concatenate, and since after each finite number of concatenations you are left with at least one language $L$ you haven't concatenated yet and which satisfies $\epsilon \not \in L$, we get that $(\circ_{L \in REG - \{\emptyset\}} L ) \cap \Sigma^*= \emptyset$. This may seem weird, but $\sum_{n \in \mathbb{N}} n = \infty \not \in \mathbb{N}$. You might even be tempted to say $\circ_{L \in REG- \{\emptyset\}} L = \emptyset$, but I'm not comfortable enough with a convergence issue here (similar to non-absolutely-convergent series, reordering the order of concatenated languages might yield different $\omega$-regular languages).
-
1$\begingroup$ Good answer, but after the OP's clarification, it's no longer relevant. It appears that the question was intended to be "Is the language of regular expressions regular?" to which, of course, the answer is "no". Too bad, since your answer was actually much more interesting, albeit for a different question. $\endgroup$ Commented Nov 17, 2015 at 15:48
-
$\begingroup$ @RickDecker Thanks, maybe it was still useful to someone :) $\endgroup$– G. BachCommented Nov 17, 2015 at 16:26
-
$\begingroup$ Yeah. As I said, your interpretation of the question was far more interesting than the new version. $\endgroup$ Commented Nov 17, 2015 at 16:35