0
$\begingroup$

I found this question in one of our past exams, and I'm not to sure about the correct answer.

I have a language L1 (which i don't know anything about) and another language L2, which is regular, the question is: given that L1L2, L2L1 are regular can i also say for sure that L1 is regular?

At first my answer was no, since I cannot say anything about the original languages given their regular concatenation; But then I thought : Wouldn't I be able to extract the DFA or regex for the first language since I have both L1L2 and L2L1?

Thank you for your time and help :)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I thought about it a bit after posting the question and came up with a counter-example for the second (and wrong) assumption:

L1 = { 0^p | p is a prime number} (Not a regular language), L2 = 0* (regular); Both the concatenations are regular since they become L1L2 = L2L1 = { 000* } ;

Thank you all for the help and for correcting my mistakes :)

Improve this answer
$\endgroup$
0
$\begingroup$

Your first answer was right I'd say. Consider L2 could be $\emptyset$. It's regular and both concatenations are equally regular. We won't learn anything about L1 though.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I also came up with a counter-example for the second answer, L1 = { 0^p | p is a prime number} (Not a regular language), L2 = 0* (regular); Both the concatenations are regular since they become L1L2 = L2L1 = { 0* } ; I Hope everything is correct. $\endgroup$
    – pezbecoding
    Commented Aug 16, 2023 at 15:55

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.