# 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.