My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)
$\begingroup$
$\endgroup$
1
asked Mar 2, 2013 at 12:03
-
$\begingroup$ The question in the title is too broad to answer. The question to the description is different and more easy to answer. $\endgroup$– Vitaly OlegovitchMar 2, 2013 at 12:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Non regular languages are closed under reverse, because $L = (L^R)^R$. Same is true for complement.
Non regular languages are not closed under most other basic operations though. Consider, for example, that $L \cup \overline{L} = \Sigma^\star$. Similarly, if $L = \{1^{x^2} | x > 1\}$ then $\overline{L} \circ \overline{L} = 1^\star$.
There is no complete list of operations on languages, so a complete answer cannot be given.
-
$\begingroup$ You (almost) have dealt with the Boolean operations $\cup, \cap, {}*c$, and with the regular operations $\cup, \cdot, {}^*$. If you add (inverse) homomorphism you cover most listed language operations, I guess. $\endgroup$ Mar 3, 2013 at 1:32
$\begingroup$
$\endgroup$
Well, if $L$ is regular, then $L^{R}$ is also regular. The contra-positive of this is that if $L^{R}$ is non-regular, then $L$ is non-regular...
