Skip to main content
3 of 5
Monotonically, not monotonously.
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

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$, the we end up with $\emptyset$. If we exclude that from the concatenation, then the length of the words in it 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} 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} 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).

G. Bach
  • 2k
  • 1
  • 17
  • 27