If $L_1$ and $L_2$ are regular then $L_1 \cup\;L_2\; = L$ is regular. Is the converse true?

782 Views Asked by At

The following is an answer I found to the question.

For instance, $\sum^*$ is a regular language; but it can be decomposed into two languages $L_1= \{0^i1^i,\;i\ge0\}$ and $L_2 = \{0^i1^j\;,\;i,j\ge0\}$, both of which are not regular.

When we say $\sum^*$ is regular, it means that every string in $\sum^*$ is accepted by some DFA. The answer say that $\sum^*$ contain strings from two non-regular languages and still be regular. How is that ?

3

There are 3 best solutions below

3
On BEST ANSWER

What you’ve quoted is false: $\{0,1\}^*$ is not the union of $L_1$ and $L_2$ as defined in that quotation. In fact $L_1\cup L_2=L_2$, which is the regular language corresponding to the regular expression $0^*1^*$. It is well-known, however, that $L_1$ is not regular; in fact it’s the standard example of a context-free language that is not regular. Thus, $L_1\cup L_2$ is an example of a regular language that is the union of a non-regular language and a regular language, though that regular language is not $\{0,1\}^*$.

Note that if $L$ is any language over the alphabet $\Sigma=\{0,1\}$, then $L\cup\Sigma^*=\Sigma^*$ is regular: it makes no difference whether $L$ is regular or not. And since there are languages $L$ over $\Sigma$ that are not regular, regularity of $L_1\cup L_2$ cannot in general imply regularity of both $L_1$ and $L_2$.

In fact it does not imply that even one of $L_1$ and $L_2$ is regular. Let $L_1=\{0^m1^n:0\le m\le n\}$ and $L_2=\{0^m1^n:m\ge n\ge 0\}$; using the pumping lemma it’s not hard to show that neither of these languages is regular. However, $L_1\cup L_2=\{0^m1^n:m,n\ge 0\}$, which is regular: as noted above, it corresponds to the regular expression $0^*1^*$. This means that although there is a DFA that accepts precisely the strings in $L_1\cup L_2$, there is no single DFA that accepts precisely the strings in $L_1$, and there is no DFA that accepts precisely the strings in $L_2$. Any DFA that accepts every string in $L_1$, for instance, necessarily accepts some strings that are not in $L_1$, and similarly for $L_2$.

0
On

You haven't phrased the situation quite right. It's not that "every $s \in \Sigma^*$ is accepted by some DFA" – that's obviously and trivially true, but isn't what it means for a subset of $\Sigma^*$ to be regular. $L \subseteq \Sigma^*$ is regular iff there is one DFA that accepts $L$ – not a possibly different DFA for each $s \in L$.

The "answer you found" is wrong. Some DFA accepts $\Sigma^*$, so it's regular. But the two languages you give do not exhaust $\Sigma^*$, and $L_2$ actually is regular: it's is just the language described by the regular expression $\mathsf{0}^*\mathsf{1}^*$. Clearly, $L_1 \subseteq L_2$. But $L_2 \neq \Sigma^*$ because for example $\mathsf{1} \mathsf{0} \notin L_2$.

However, it is true that if $L \subseteq \Sigma^*$ is regular, then so is $\Sigma^* \setminus L$. Thus if $L \subseteq \Sigma^*$ is not regular, then neither is $\Sigma^* \setminus L$ (why?). By the Pumping Lemma, $L_1$ is not regular; so take $L_2 = \Sigma^* \setminus L_1$.

Thus, the converse is false.

0
On

When we say $\sum^*$ star is regular, we are saying that there is a single DFA which accepts exactly the strings within. However, it can be decomposed into two sets $L_1$ and $L_2$ such that there is no DFA accepting exactly the strings in $L_1$ (or in $L_2$).

That is, remember that "regular" applies to the whole language, not to the words within. You seem to be thinking "A language is regular if every string within is regular" which is not true, since there is no notion of a string being regular (as every string is accepted by some DFA). Rather, we might say "A language is regular if it is not too complicated a set of strings" - so the idea is to take a simple language $\sum^*$ and break it up into two complicated pieces.