Odległość między zwykłymi językami

Chcę zdefiniować pojęcie „bliskości” między dwoma regularnymi językami skończonych słów w (i / lub nieskończonych słów w ). Podstawową ideą jest to, że chcemy, aby dwa języki były blisko siebie, jeśli nie różnią się wieloma słowami. Możemy również w jakiś sposób wykorzystać odległość edycji ... Nie mogłem znaleźć dobrych referencji na ten temat. $\Sigma^*$ $\Sigma^\omega$

Nie nazywam tego odległością, ponieważ nie wymagam, aby wszystkie aksjomaty odległości były prawdziwe (choć nie jest źle, jeśli tak jest).

Pierwszą próbą jest zdefiniowanie gdzieisą ograniczeniamiido, ajest różnicą symetryczną.

d (L, K) = \underset{n \to \infty}{lim sup} \frac{| L_{n} Δ K_{n} |}{| L_{n} \cup K_{n} |}

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

L_{n}

$L_n$

K_{n}

$K_n$

L

$L$

K

$K$

Σ^{n}

$\Sigma^n$

Δ

$\Delta$

Czy badana jest ta „odległość”? Czy istnieją odniesienia do tego tematu (ewentualnie z alternatywnymi opcjami funkcji odległości)? Dziękujemy za pomoc lub wskaźnik, dzięki.

reference-request fl.formal-languages regular-language

— Denis
źródło

Jak zapewne już wiesz, powszechną miarą słów jest metryka Cantora, która jest zdefiniowana jako:

d (l, k) = {\begin{cases} 0 & if l = k \\ 2^{- n} & where n = min {i \in N | l_{i} \neq k_{i}} \end{cases}

$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.$

$2^{-n}$ $n$

Ten wskaźnik pokazuje się bardzo często w weryfikacji. Pierwsze odniesienie do tego, które znam, to Alpern i Schneider 1985, Defining Livity . (Przepraszam za brak linku, ale nie mogłem znaleźć kopii online.)

Jean-Eric Pin napisał artykuł ankietowy, Profinite Methods in Automata Theory , w którym bada kilka bardziej ogólnych wskaźników, a także nawiązuje do dualności kamienia.

— Neel Krishnaswami
źródło

Dzięki, zdawałem sobie sprawę z metryki Cantora, ale nie z jej użycia do definiowania metryki Hausdorffa, wydaje się to zupełnie w porządku.

— Denis