Proving the language which consists of all strings in some language is the same length as some string in another language is regular

Question

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose length is equal to some string in $B$ is a regular language.

In equation form:

$$L = \{x \in A \mid \exists y \in B \text{ s.t. } |x| = |y| \}$$

My initial thought was to try and come up with some DFA for both languages $A$ and $B$ and map the two states to each other and hopefully get a 1:1 ratio that way I can generate a new DFA which proves that $L$ is regular. But then I realized that $A$ and $B$ don't have to be over the same set of symbols.

I think the correct way to solve this is to use the closure properties of regular language, but I'm not sure of how to begin/use the properties for "lengths" of strings instead of strings themselves.

Could someone point me in the right direction?

Answer 1

Remember (or come up with) the proof for

$\qquad \displaystyle L_1, L_2 \in \mathsf{REG} \implies L_1 \cap L_2 \in \mathsf{REG}$.

Do you see how to modify the proof for your setting?

Abstracting the equality of lengths thing, come up with a construction for an automaton for

$\qquad \displaystyle L_l = \{ w \in \Sigma^* \mid \exists x \in L.\, |x|=|w|\}$

for given, arbitrary $L \in \mathsf{REG}$ over $\Sigma$.

Do you see the connection?

Now note that $L = A \cap B_l$.

Answer 2

Hints: Let's assume you know all the different lengths of words in $B$, $len(B) = \{ \ell_1, \ell_2, \ell_3, ... \}$. For the time being, let's assume it is finite.

Can you use this knowledge to construct a DFA for $A$?
^{(hint: intersection, or "cross-product" construction)}

Does the alphabet of $B$ even matters?

Next, it might be the the set of lengths $len(B)$ is infinite. Then look at this question which should resolve that matter as well.

Answer 3

The closure property way, so no (explicit) automata. Regular languages are closed under morphisms, inverse morphisms and intersection (with regular languages).

Let $\Sigma_A$ and $\Sigma_B$ be the alphabets of $A$ and $B$. Let $h_X:\Sigma_X^* \to \{1\}^*$ be the morphism that maps every letter $a\in\Sigma_X$ to $1$. Then $h_B(B) \subseteq \{1\}^*$ codes the length set of $B$, and $h_A^{-1}(h_B(B))$ consists of (all) strings that are of the same length as strings in $B$, but over the alphabet of $A$. Finally, we observe that $L= A\cap h_A^{-1}(h_B(B))$.

Now for the bonus. It also works for context-free $A$ and $B$. We need however an additional property: if $B$ is context-free then $h_B(B)$ is regular (!) as all 'unary' (=single letter alphabet) context-free languages are regular, a consequence of Parikh's theorem. Thus also $h_A^{-1}(h_B(B))$ is regular, and $L$ is context-free.