Proof that truncation of a regular language is regular


Let $ L_1$ be a regular language and $ L_2$ any language. I want to prove that the language of $ L_1$ truncated by $ L_2$ is a regular language, i.e.

$ $ \{w| wx\in L_1 \text{ and } x\in L_2\}$ $

is regular.

To prove that something is regular it is enough to prove that it is described by a regular expression. We know that $ L_1$ is described by a regular expression, but regular expressions don’t handle "differences" in any obvious way.

We could imagine the DFA which accepts exactly the strings of $ L_1$ . But to truncate the strings of $ L_2$ we would need some way of recognizing the portions of the tail of the word which are in $ L_2$ and there may be no DFA which does this. Likewise for any recognizing DFA.

In general it’s hard to imagine having "any language" interact with a regular language to produce a regular language. The "any language" isn’t constrained by any of the tools that seem relevant to regular languages, like NFAs and regular expressions.