8
$\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 to?

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!

Thank you!

$\endgroup$
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$
  • $\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$ – David Richerby 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$ – David Richerby Dec 4 '15 at 20:55
  • 1
    $\begingroup$ @stud1 Correct. $\endgroup$ – David Richerby 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$
  • 1
    $\begingroup$ Elegant solution! $\endgroup$ – Anton Trunov 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$
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.