Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular.

I need some help on getting started on proving this is the case.

My intuition is that if $L_1 \cdot L_2$ is regular there exists a DFA for it, in which case you can just remove the states that correspond to the $L_2$ part of the DFA and you are left with a DFA that recognizes $L_1$.

  • 1
    $\begingroup$ 1) Your title did not represent the question at all. 2) You can use LaTeX here. 3) Have you tried applying your idea to a simple example? What do you observe? 4) Are you familiar with the left-/right-quotient of languages? $\endgroup$ – Raphael Oct 9 '14 at 18:12
  • $\begingroup$ 1) Sorry 2) OK 3) Yes, it wasnt obvious to make 4) I looked up the definitions and understand them $\endgroup$ – QIANG Oct 9 '14 at 18:16
  • $\begingroup$ for your concrete question, try drawing down the DFA and see what you can find. $\endgroup$ – xiamx Oct 9 '14 at 18:42
  • 1
    $\begingroup$ The problem with your intuition is that you don't know if the DFA can be divided into an L1 part and an L2 part. $\endgroup$ – reinierpost Oct 10 '14 at 9:26

Suppose that $L_2 = \Sigma^*$ and $L_1$ includes the empty string. Then $L_1 \cdot L_2 = \Sigma^*$, yet $L_1$ doesn't even have to be computable.

  • $\begingroup$ Are you saying that generalized that the first part of a concatenation is always regular if the concatenation is regular? I know examples where $L_{1}$ is non-regular and the concatenation is regular $\endgroup$ – QIANG Oct 9 '14 at 18:18
  • 2
    $\begingroup$ I'm saying that your statement is false. $\endgroup$ – Yuval Filmus Oct 9 '14 at 18:19
  • $\begingroup$ We are given L2 as a regular expression $\endgroup$ – QIANG Oct 9 '14 at 18:21
  • 1
    $\begingroup$ I gave an example in which $L_2$ is regular and infinite, $L_1 \cdot L_2$ is regular, yet $L_1$ is not regular. For concreteness, let $L_1$ consist of the empty string plus all encodings of Turing machines that halt on the empty input. $\endgroup$ – Yuval Filmus Oct 9 '14 at 18:22
  • $\begingroup$ OK I updated question a bit thats less general $\endgroup$ – QIANG Oct 9 '14 at 18:30

Let $L_1 = a^p$ such that $p$ is prime, let $L_2 = a^*$ then $L_2$ and $L_1 \cdot L_2$ are both regular, but $L_1$ is not


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.