Abstand

Einfache Sprache

Im Kontext von Formalen Sprachen gibt der Abstand wieder wie sehr sich zwei Wörter am Ende unterscheiden.

Def. Abstand

Seien $x$ und $y$ beliebige Wörter und sei $u$ das maximale gemeinsame Präfix] von $x$ und $y$. Dann lassen sich $x$ und $y$ schreiben als $x = ux_0$ und $y = uy_0$. Der Abstand von $x$ und $y$, in Zeichen $d(x,y)$, ist dann gegeben durch

$$d(x,y) = |x_0| + |y_0| = |x| + |y| -2|\text{lcp}(x,y)|\;.$$