$L_1$ and $L_2$ are regular and we have a new language $\text{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2\text{ s.t. }xu\in L_1\}$

Question

1. prove that $\operatorname{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2 \text{ such that $xu\in L_1$}\}$ is regular.

So I was thinking proving this question by building an automata for pref but couldn't do it really much. than using closure properties but I couldn't really think of any that will help aside of a homomorphic function which I don't know how to build.

2. prove or disprove that if only $L_1$ is regular than pref is regular

Here again using closure properties but cant really think of any.

Thank you.

Answer 1

This is true for all languages $L_2$, regular or not. Recall that if $L$ is a language and $u$ is a word, $$ Lu^{-1} = \{v \in \Sigma^* \mid vu \in L\}. $$ Hint. Use the fact that, for every regular language $L$, there are only finitely many distinct languages of the form $Lu^{-1}$, all of them regular.

Hint 2. $$ \operatorname{pref}(L_1,L_2) = \bigcup_{u \in L_2}Lu^{-1} $$