Skip to main content
Fixed a typo: changed a "languages" to "strings" and fixed some grammar.
Source Link

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

Try to think on complements of known non-regular languages.

Solution:

Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the languagesstrings EXCEPT for those that in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now letslet's think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^*$ is regular, we are done.

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

Try to think on complements of known non-regular languages.

Solution:

Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the languages EXCEPT for those that in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now lets think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^*$ is regular, we are done.

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

Try to think on complements of known non-regular languages.

Solution:

Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the strings EXCEPT for those in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now let's think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^*$ is regular, we are done.

Source Link
Ran G.
  • 20.8k
  • 3
  • 60
  • 116

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

Try to think on complements of known non-regular languages.

Solution:

Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the languages EXCEPT for those that in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now lets think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^*$ is regular, we are done.