2
$\begingroup$

Let $L_1 = \{ a^{n}b^{m} \mid n > m > 0 \} $. Describe a non-regular language $L_2$ such that $L_3 = L_1 \cup L_2$ is regular and $L_3 ≠ A^{*}$ (where $A = \{ a, b \} $)

From the trace, I cannot prove this with the simple language of $L= \{ a^{n}b^{m} \mid n,m > 0 \} $ since it must be different from $A^{*}$.

I had thought of $L_2 = \{ a^{n}b^{m} \mid n ≤ m \} \setminus \{ aab \} $, so in this way we do not consider a string of $L_1$ and the union is different from $A^{*}$

$\endgroup$
1
  • 4
    $\begingroup$ Your choice of $L2$ looks good (but what are you trying to achieve with that ${}-\{aab\}$? After all $aab\notin\{\,a^nb^m\mid n\le m\,\}$) - where are you stuck? $\endgroup$ Jan 5 at 21:13

3 Answers 3

6
$\begingroup$

Let $L_2 = A^* \setminus (L_1\cup \{\varepsilon\})$. Then $L_1 \cup L_2 = A^*\setminus \{\varepsilon\}$ which is regular and not equal to $A^*$.

$\endgroup$
8
  • $\begingroup$ and is it equivalent to writing that $L3 = a^{n} b^{m} | n,m > 0 }$ since there is no empty string in $L1$ or $L2$? ($n,m> 0$) $\endgroup$
    – Luca
    Jan 5 at 14:35
  • $\begingroup$ No, because there is no obligations for $b$'s to necessarily follow $a$'s. For example, $baba$ is a word of $L_3$ in my case. $\endgroup$
    – Nathaniel
    Jan 5 at 14:36
  • $\begingroup$ Right, I got confused. So it would have been correct to combine $L1 = ${$ a^{n} b^{m} | n > m > 0 $}$ $ with $L2 = ${$ a^{n}b^{m} | n <= m $}$ $ and get $L3 = ${$ a^{n} b^{m} | n,m > 0 $}$ $ which is regular? $\endgroup$
    – Luca
    Jan 5 at 14:42
  • $\begingroup$ If you meant $0 < n \leqslant m$ in $L_2$, then yes. $\endgroup$
    – Nathaniel
    Jan 5 at 14:49
  • $\begingroup$ Yes I mean that, thank you now it is clear I was confused about the definition of A* $\endgroup$
    – Luca
    Jan 5 at 14:51
5
$\begingroup$

Nowhere does the question state that the intersection of $L1$ and $L2$ must be empty.

Also for L1 to contain the empty string it must be that $m = n =0$ in the description, however $m,n >0$, therefore $L1$ doesn't contain the empty string.

The obvious solution is for $L3 = \{ a^*b^* \}$ (using kleene star) And then figuring out which non-regular language is a superset of $L3\setminus L1$.

Though technically saying $L2 = \{ a^*b^* \} \setminus L1$ is a sufficient solution assuming they can prove that it is non-regular (which you can do using the fact that intersection, complement and union operations are closed under regular languages). But it's simpler to simply take the $\{ a^{n}b^{m} | n <= m\}$ because that fills in all missing pairs of n and m that are missing from $L1$.

$\endgroup$
0
3
$\begingroup$

If you don't want $L_2$ to be the complement of $L_1$ (as then $L_3$ would the set of all words), then you can simply choose $L_2$ to be $\overline{L_1}\setminus L$, where $L$ is a nonempty finite language that is contained in $\overline{L_1}$.

Correctness follows from standard closure properties of regular languages, and from the fact that every finite language is regular. So you get in total that $$(\overline{L_1}\setminus L) \cup L = \overline{L_1}$$ Hence, since $L\in \text{REG}$ and $\overline{L_1}\notin \text{REG}$, we get from regular languages being closed under union that $\overline{L_1}\setminus L\notin \text{REG}$. Then, the union $(\overline{L_1}\setminus L) \cup L_1 = A^* \setminus L = \overline{L}$ is regular.

Note: In any problem where you are asked to come up with a regular or a non-regular language, then adding or subtracting a finite language from the answer won't change it as regular languages are closed under complementation, intersection (and hence difference -- think why) and union. This is useful in particular for this annoying edge cases where you get a correct answer up to a finite number of words.

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