-3
$\begingroup$

Does there exist languages $L1$, $L2$ where $L1$ is non regular, $L2$ is regular $L1\not\subset L2$ and $L1 \cup L2$ is regular?

$\endgroup$

closed as off-topic by Hsien-Chih Chang 張顯之, Sasho Nikolov, Marzio De Biasi, Emil Jeřábek, Aryeh Feb 13 '18 at 11:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Hsien-Chih Chang 張顯之, Sasho Nikolov, Marzio De Biasi, Emil Jeřábek, Aryeh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ why the downvote? $\endgroup$ – Torsten Gang Feb 13 '18 at 1:15
0
$\begingroup$

I'm going by the question in the title, i.e., that $L_1\not\subset L_2$. In the body of the question you instead wrote $L_1\subsetneq L_2$ which would in contrast mean that $L_1$ is a strict subset of $L_2$.

Let $L_1$ be any non-regular language. Let $x\in L_1$ be some element of $L_1$. Then set $L_2 = \Sigma\setminus\{x\}$.

  1. $L_2$ is clearly regular, since there's a trivial NFA for it that accepts any word except $x$.
  2. $L_1$ is by definition not regular.
  3. $L_1\setminus L_2=\{x\}\neq\emptyset$ and therefore $L_1 \not\subset L_2$
  4. $L_1\cup L_2 = \Sigma$ which is clearly a trivial regular language.
$\endgroup$

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