Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?

  • $\begingroup$ Yes it is regular. $\endgroup$
    – Nathaniel
    Dec 6, 2021 at 18:45
  • 2
    $\begingroup$ (Now if you want a better answer, you should try to improve your post: formatting, what you tried, your thoughts about the problem, …) $\endgroup$
    – Nathaniel
    Dec 6, 2021 at 18:47
  • $\begingroup$ but if i dont know anything. please help to prove it that languagee is regular $\endgroup$
    – user144938
    Dec 6, 2021 at 19:38
  • 2
    $\begingroup$ Here's an introduction to formatting math on this site: math.meta.stackexchange.com/questions/5020/… $\endgroup$
    – rici
    Dec 6, 2021 at 20:00
  • 1
    $\begingroup$ Does this answer your question? Closure against right quotient with a fixed language $\endgroup$
    – xskxzr
    Dec 7, 2021 at 8:31

1 Answer 1


The prefix language of $L$ is the set of all prefixes of strings in $L$, $\{w\mid \exists v \in \Sigma^*, wv\in L\}$. In other words, it is the right quotient of $L$ with $\Sigma^*$, so it is certainly regular if $L$ is regular, by closure with right quotient.

A possibly simpler way to see this is to observe that you can construct a recogniser for the prefix language of $L$ by constructing the minimal DFA for $L$ and then making all states accepting.

Your language is the intersection of $L_1$ with the prefix language of $L_2$. Since regular languages are also closed with intersection, it must be regular if $L_1$ and $L_2$ are both regular.


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.