Membuktikan bahasa yang terdiri dari semua string dalam beberapa bahasa sama panjangnya dengan beberapa string dalam bahasa lain biasa

Jadi saya sudah menggaruk-garuk kepala karena masalah ini selama beberapa hari sekarang. Diberi beberapa bahasa$A$dan yang teratur, menunjukkan bahwa bahasa yang terdiri dari semua string dalam yang panjangnya sama dengan beberapa string dalam adalah bahasa biasa.$B$$L$$A$$B$

Dalam bentuk persamaan:

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

Pikiran awal saya adalah mencoba dan menghasilkan beberapa DFA untuk kedua bahasa dan dan memetakan kedua negara satu sama lain dan mudah-mudahan mendapatkan rasio 1: 1 dengan cara itu saya dapat menghasilkan DFA baru yang membuktikan bahwa teratur. Tapi kemudian saya menyadari bahwa dan tidak harus lebih dari set simbol yang sama. $A$$B$$L$$A$$B$

Saya pikir cara yang benar untuk menyelesaikan ini adalah dengan menggunakan properti penutupan bahasa biasa, tapi saya tidak yakin bagaimana memulai / menggunakan properti untuk "panjang" string, bukan string sendiri.

Bisakah seseorang mengarahkan saya ke arah yang benar?

Ingat (atau buktikan) buktinya

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

Apakah Anda melihat cara memodifikasi bukti untuk pengaturan Anda?

Abstraksi kesetaraan hal panjang, datang dengan konstruksi untuk otomat untuk

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

untuk diberikan, sewenang-wenang $L \in \mathsf{REG}$ lebih $\Sigma$.

Apakah Anda melihat hubungannya?

Sekarang perhatikan itu $L = A \cap B_l$.

Petunjuk: Mari kita asumsikan Anda tahu semua panjang kata yang berbeda di$B$, $len(B) = \{ \ell_1, \ell_2, \ell_3, ... \}$. Untuk saat ini, mari kita asumsikan itu terbatas.

Bisakah Anda menggunakan pengetahuan ini untuk membuat DFA? $A$?
^{(petunjuk: persimpangan, atau konstruksi "lintas produk")}

Apakah alfabet $B$ bahkan penting?

Selanjutnya, mungkin set panjang $len(B)$tidak terbatas. Kemudian lihat pertanyaan ini yang harus menyelesaikan masalah itu juga.

Cara properti penutupan, jadi tidak ada (eksplisit) automata. Bahasa reguler ditutup di bawah morfisme, morfisme terbalik, dan persimpangan (dengan bahasa reguler).

Membiarkan $\Sigma_A$ dan $\Sigma_B$ menjadi huruf dari $A$ dan $B$. Membiarkan$h_X:\Sigma_X^* \to \{1\}^*$ menjadi morfisme yang memetakan setiap huruf $a\in\Sigma_X$ untuk $1$. Kemudian$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.