Provar que o idioma que consiste em todas as strings em algum idioma tem o mesmo tamanho que um string em outro idioma

Então, eu estou coçando a cabeça sobre esse problema há alguns dias. Dada uma linguagem regular e , mostre que a linguagem que consiste em todas as strings em cujo comprimento é igual a alguma string em é uma linguagem regular.$A$$B$$L$$A$$B$

Em forma de equação:

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

Meu pensamento inicial era tentar criar algum DFA para os dois idiomas e e mapear os dois estados entre si e, esperançosamente, obter uma proporção de 1: 1 para que eu possa gerar um novo DFA que comprove que é regular. Mas então eu percebi que e não precisam ter o mesmo conjunto de símbolos. $A$$B$$L$$A$$B$

Eu acho que a maneira correta de resolver isso é usar as propriedades de fechamento da linguagem regular, mas não tenho certeza de como iniciar / usar as propriedades para "comprimentos" de seqüências de caracteres, em vez de elas próprias.

Alguém poderia me apontar na direção certa?

Lembre-se (ou crie) a prova de

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

Você vê como modificar a prova da sua configuração?

coisa da igualdade de comprimentos, uma construção para um autômato para por dado, arbitrário sobre .

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

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

Você vê a conexão?

Agora observe que .$L = A \cap B_l$

Dicas: Vamos supor que você saiba todos os diferentes comprimentos de palavras em , . Por enquanto, vamos assumir que é finito.$B$$len(B) = \{ \ell_1, \ell_2, \ell_3, ... \}$

Você pode usar esse conhecimento para construir um DFA para ? ^{(dica: interseção ou construção "produto cruzado")}$A$

O alfabeto de importa mesmo?$B$

Em seguida, pode ser que o conjunto de comprimentos seja infinito. Então olhe para esta pergunta que deve resolver esse problema também.$len(B)$

A maneira de propriedade de fechamento, portanto, não há autômatos (explícitos). Linguagens regulares são fechadas sob morfismos, morfismos inversos e interseção (com linguagens regulares).

Vamos e ser os alfabetos de e . Seja o morfismo que mapeia todas as letras de para . Então codifica o conjunto de comprimentos de e consiste em (todas) seqüências de caracteres que têm o mesmo comprimento que as seqüências de caracteres em , mas sobre o alfabeto de . 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))$

Agora, o bônus . Também funciona para e sem contexto . No entanto, precisamos de uma propriedade adicional: se é livre de contexto, então é regular (!) , todas as línguas livres de contexto 'unárias' (= alfabeto de uma letra) são regulares, uma consequência do teorema de Parikh . Assim, também é regular e é livre de contexto.$A$$B$$B$$h_B(B)$$h_A^{-1}(h_B(B))$$L$