Abstand zwischen regulären Sprachen

13

Ich mag einen Begriff der „Nähe“ zwischen zwei regulären Sprachen endlicher Worte definieren (und / oder unendlichen Worten Σ & ohgr; ). 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.ΣΣω

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, wobeiLnundKndie Restriktionen vonLundKbisΣnsind undΔdie symmetrische Differenz ist.

d(L,K)=lim supn|LnΔKn||LnKn|
LnKnLKΣnΔ

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.

Denis
quelle

Antworten:

11

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)={0wenn l=k2-nwo n=Mindest{ichN|lichkich}

2-nn

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