1
$\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$
  • $\begingroup$ The question in the title is too broad to answer. The question to the description is different and more easy to answer. $\endgroup$ – Виталий Олегович Mar 2 '13 at 12:12
7
$\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$
  • $\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$ – Hendrik Jan Mar 3 '13 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, privacy policy and cookie policy

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