-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$
  • $\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.