Jarak antara bahasa biasa

Saya ingin mendefinisikan pengertian "kedekatan" antara dua bahasa reguler dari kata-kata terbatas dalam $\Sigma^*$ (dan / atau kata-kata tak terbatas dalam ). Ide dasarnya adalah bahwa kita ingin dua bahasa menjadi dekat jika mereka tidak berbeda dengan banyak kata. Kami juga dapat menggunakan jarak sunting dalam beberapa cara ... Saya tidak dapat menemukan referensi yang bagus tentang masalah ini.$\Sigma^\omega$

Saya tidak menyebutnya jarak karena saya tidak memerlukan semua aksioma jarak untuk menjadi kenyataan (meskipun tidak buruk jika itu).

Upaya pertama adalah mendefinisikan mana dan adalah batasan dan ke , dan adalah perbedaan simetris.

$$d(L,K)= \limsup_{n\to\infty} \frac{|L_n\Delta K_n|}{|L_n\cup K_n|}$$ $L_n$$K_n$$L$$K$$\Sigma^n$$\Delta$

Apakah "jarak" ini dipelajari? Apakah ada referensi pada subjek (mungkin dengan pilihan alternatif untuk fungsi jarak)? Bantuan atau penunjuk apa pun akan dihargai, terima kasih.

Seperti yang mungkin sudah Anda ketahui, metrik umum pada kata-kata adalah metrik Cantor, yang didefinisikan sebagai:

$$d(l, k) = \left\{ \begin{array}{ll} 0 & \mbox{if } l = k \\ 2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\} \end{array} \right.$$

Secara kasar, jika string adalah urutan peristiwa, jarak antara dua string adalah , di mana adalah pertama kalinya mereka berbeda. Ini dapat diangkat ke metrik pada bahasa (yang tidak kosong) dengan menggunakan metrik Hausdorff. (Jika Anda mengizinkan string tanpa batas, Anda juga harus memastikan bahwa bahasa tersebut lengkap dengan Cauchy.) $2^{-n}$$n$

Metrik ini banyak muncul dalam verifikasi. Referensi pertama yang saya tahu adalah Alpern dan Schneider 1985, Defining Liveness . (Maaf karena tidak ada tautan, tetapi saya tidak dapat menemukan salinan daring.)

Jean-Eric Pin telah menulis artikel survei, Metode Tak Terbatas dalam Teori Automata , di mana ia mensurvei beberapa metrik yang lebih umum, dan juga menarik beberapa koneksi ke dualitas Batu.