Abstand zwischen regulären Sprachen

Ich mag einen Begriff der „Nähe“ zwischen zwei regulären Sprachen endlicher Worte definieren (und / oder unendlichen Worten ). Die Grundidee ist, dass zwei Sprachen nahe beieinander sein sollen, wenn sie sich nicht durch viele Wörter unterscheiden. Wir könnten auch die Bearbeitungsentfernung in irgendeiner Weise verwenden ... Ich konnte keine guten Referenzen zu diesem Thema finden. $\Sigma^*$ $\Sigma^\omega$

Ich nenne es keine Distanz, weil ich nicht alle Distanzaxiome für wahr halte (obwohl es nicht schlecht ist, wenn sie wahr sind).

Ein erster Versuch besteht darin, wobeiunddie Restriktionen vonundbissind unddie symmetrische Differenz ist.

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$

Wird diese "Distanz" untersucht? Gibt es Referenzen zu diesem Thema (möglicherweise mit alternativen Auswahlmöglichkeiten für die Distanzfunktion)? Jede Hilfe oder Hinweis wäre dankbar, danke.

reference-request fl.formal-languages regular-language Denis
quelle

Antworten:

Wie Sie vielleicht bereits wissen, ist eine gängige Metrik für Wörter die Cantor-Metrik, die wie folgt definiert ist:

d (l, k) = {\begin{cases} 0 & wenn l = k \\ 2^{- n} & wo n = Mindest {ich \in N | l_{ich} \neq k_{ich}} \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$

Diese Metrik zeigt sich viel in der Verifikation. Der erste Hinweis darauf, den ich kenne, ist Alpern und Schneider 1985, Defining Liveness . (Entschuldigung für das Fehlen eines Links, aber ich konnte keine Online-Kopie finden.)

Jean-Eric Pin hat einen Übersichtsartikel mit dem Titel Profinite Methods in Automata Theory geschrieben , in dem er einige allgemeinere Metriken untersucht und auch einige Verbindungen zur Stone-Dualität herstellt.

Neel Krishnaswami
quelle

Vielen Dank, ich war mir der Cantor-Metrik bewusst, aber nicht ihrer Verwendung für die Definition der Hausdorff-Metrik. Dies scheint vollkommen in Ordnung zu sein.

Denis