2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The question in the title is too broad to answer. The question to the description is different and more easy to answer. $\endgroup$ Commented Mar 2, 2013 at 12:12

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Mar 3, 2013 at 1:32
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.