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!

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
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.

Improve this answer
$\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, 2015 at 17:35
  • 1
    $\begingroup$ @stud1 To ensure that $L_1L_2$ is regular. $\endgroup$
    – David Richerby
    Dec 4, 2015 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, 2015 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$
    – David Richerby
    Dec 4, 2015 at 20:55
  • 1
    $\begingroup$ @stud1 Correct. $\endgroup$
    – David Richerby
    Dec 4, 2015 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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Elegant solution! $\endgroup$
    – Anton Trunov
    Dec 4, 2015 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, 2015 at 17:43
  • $\begingroup$ What id the meaning of $+$ at $11^+$? $\endgroup$
    – stud1
    Dec 4, 2015 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, 2015 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.

Improve this answer
$\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*

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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