Probar que el idioma que consta de todas las cadenas en algún idioma tiene la misma longitud que alguna cadena en otro idioma es regular

Así que llevo unos días rascándome la cabeza sobre este problema. Dado un lenguaje y que es regular, demuestre que el lenguaje que consiste en todas las cadenas en cuya longitud es igual a alguna cadena en es un lenguaje regular.$A$$B$$L$$A$$B$

En forma de ecuación:

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

Mi pensamiento inicial fue tratar de encontrar algunos DFA para ambos idiomas y y mapear los dos estados entre sí y, con suerte, obtener una relación 1: 1 de esa manera puedo generar un nuevo DFA que demuestre que es regular. Pero luego me di cuenta de que y no tienen que estar sobre el mismo conjunto de símbolos. $A$$B$$L$$A$$B$

Creo que la forma correcta de resolver esto es usar las propiedades de cierre del lenguaje normal, pero no estoy seguro de cómo comenzar / usar las propiedades para "longitudes" de cadenas en lugar de las cadenas en sí.

¿Podría alguien señalarme en la dirección correcta?

Recuerde (o presente) la prueba de

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

¿Ves cómo modificar la prueba para tu configuración?

la igualdad de longitudes, una construcción para un autómata para para dado, arbitrario sobre .

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

$L \in \mathsf{REG}$$\Sigma$

Ves la conexion?

Ahora tenga en cuenta que .$L = A \cap B_l$

Sugerencias: supongamos que conoce todas las diferentes longitudes de palabras en , . Por el momento, supongamos que es finito.$B$$len(B) = \{ \ell_1, \ell_2, \ell_3, ... \}$

¿Puedes usar este conocimiento para construir un DFA para ? ^{(sugerencia: intersección o construcción de "producto cruzado")}$A$

¿El alfabeto de incluso importa?$B$

A continuación, podría ser que el conjunto de longitudes sea ​​infinito. Luego mire esta pregunta que también debería resolver ese asunto.$len(B)$

La forma de propiedad de cierre, por lo que no hay autómatas (explícitos). Los lenguajes regulares están cerrados bajo morfismos, morfismos inversos e intersección (con lenguajes regulares).

Deje y sean los alfabetos de y . Deje que sea ​​el morfismo que asigna cada letra a . Entonces codifica el conjunto de longitud de , y consta de (todas) cadenas que tienen la misma longitud que las cadenas de , pero con el alfabeto de la . Finalmente, observamos que .$\Sigma_A$$\Sigma_B$$A$$B$$h_X:\Sigma_X^* \to \{1\}^*$$a\in\Sigma_X$$1$$h_B(B) \subseteq \{1\}^*$$B$$h_A^{-1}(h_B(B))$$B$$A$$L= A\cap h_A^{-1}(h_B(B))$

Ahora para la bonificación . También funciona para y sin contexto . Sin embargo, necesitamos una propiedad adicional: si está libre de contexto, entonces es regular (!) que todos los lenguajes libres de contexto 'unarios' (= alfabeto de una sola letra) son regulares, una consecuencia del teorema de Parikh . Por lo tanto, también es regular y tiene contexto.$A$$B$$B$$h_B(B)$$h_A^{-1}(h_B(B))$$L$