Skip to main content
added 1 character in body
Source Link
G. Bach
  • 2k
  • 1
  • 17
  • 27

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

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 - \{\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).

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).

added 31 characters in body
Source Link
G. Bach
  • 2k
  • 1
  • 17
  • 27

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$$(\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} L = \emptyset$$\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).

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).

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 - \{\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).

Monotonically, not monotonously.
Source Link
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 monotonouslymonotonically 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).

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 monotonously 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).

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).

added 780 characters in body
Source Link
G. Bach
  • 2k
  • 1
  • 17
  • 27
Loading
Source Link
G. Bach
  • 2k
  • 1
  • 17
  • 27
Loading