9
$\begingroup$

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular too?

I try to find a way to prove it...

I can't assume of course that $L_1,L_2$ are regular...
So I look for a way to prove it.

I'd like to get any hint!

$\endgroup$
1
7
$\begingroup$

No, $L_2L_1$ is not necessarily regular.

Let $L_1 = \{0,1\}^*$, which is regular, and $L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$, which is not. Then $L_1L_2$ is the set of all strings ending with $1$, which is regular, but $L_2L_1$ is the set of all strings that either begin with $1$, begin with a nonzero number of $0$s followed by at least as many $1$s. This language is not regular, since its intersection with $\{0^m1^n\mid m,n\geq 1\}$ is $\{0^m1^n\mid 1\leq m\leq n\}$, which is non-regular.

$\endgroup$
6
  • $\begingroup$ Thank you David, but why is the "$\{1\}\cup \cdots$" at $L_2$? why we need it? Thank you! $\endgroup$
    – stud1
    Dec 4 '15 at 17:35
  • 1
    $\begingroup$ @stud1 To ensure that $L_1L_2$ is regular. $\endgroup$ Dec 4 '15 at 17:38
  • $\begingroup$ But $L_1L_2$ (without the $\{1\}$) it's still all the words that ends with $1$, right? So, I still try to understand why we need the $\{1\}$, I hope it's OK I'm asking it :-) Thank you! $\endgroup$
    – stud1
    Dec 4 '15 at 19:53
  • 1
    $\begingroup$ @stud1 If you delete $\{1\}$ then, for example, $1\notin L_1L_2$. More generally, the only strings that would be in $L_1L_2$ would be the ones ending in $0^mw^n$ for $m\geq n\geq 1$. $\endgroup$ Dec 4 '15 at 20:55
  • 1
    $\begingroup$ @stud1 Correct. $\endgroup$ Dec 4 '15 at 23:04
13
$\begingroup$

I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)

Let $L_1 = \{ 1^p \mid p \text{ is prime}\}$, $L_2 = \{ 1^* 0 \}$; we have $L_1 L_2 = \{ 11^+ 0\}$ which is regular, but $L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$ which is not regular.

$\endgroup$
4
  • 1
    $\begingroup$ Elegant solution! $\endgroup$ Dec 4 '15 at 17:40
  • 2
    $\begingroup$ @AntonTrunov: quite elegant :-) $L_2 = \{1^* 0\}$ can be used to "mask" any non-regular UNARY $L_1$, but as soon as they are swapped $L_1$ is "exposed" again :-) $\endgroup$
    – Vor
    Dec 4 '15 at 17:43
  • $\begingroup$ What id the meaning of $+$ at $11^+$? $\endgroup$
    – stud1
    Dec 4 '15 at 19:55
  • 1
    $\begingroup$ @stud1: $1^+$ means "one or more $1s$"; in other words it is a "shortcut" for $\{1^n \mid n \geq 1\}$. So $\{ 11^+0 \} = \{ 110, 1110, 11110, ...\}$ $\endgroup$
    – Vor
    Dec 5 '15 at 1:30
6
$\begingroup$

This is not a hint, but a full answer. Don't read on if you're still trying to solve.

There is no need for $L_2\cdot L_1$ to be regular.

Let $A$ be a unary (non-regular) language such that $A\cdot A$ is regular. Such languages can be found in the post here. Assume $A$ is over the alphabet $\{a\}$.

Define $L_1=\{b\}\cdot A$ and $L_2=A\cdot \{b\}$. Then, you get $L_1\cdot L_2=\{b\}\cdot A^2\cdot \{b\}$, which is regular. However, $L_2\cdot L_1=A\cdot \{bb\}\cdot A$, which can be easily proven to be non-regular, based on $A$ being non-regular.

$\endgroup$
0
1
$\begingroup$

The following rules define the language associated with any regular expression. Rule 1 The language associated with the regular expression that is just a single letter is that one-letter word alone and the language associated with A is just {A}, a one-word language. Rule 2 If r, is a regular expression associated with the language L, and r 2 is a regular expression associated with the language L2 then,

(i) The regular expression (rl) (r2) is associated with the language L, times L 2. language (r, r2) = L1L 2 (ii) The regular expression r, + r2 is associated with the language formed by the union of the sets L1 and L2. language (rl + r2) = L, + L2 (iii) The language associated with the regular expression (rl)* is LI*, the Kleene closure of the set LI as a set of words. language (rl*) = L1*

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