L(G) formale Darstellung

Question

Hallo,

die in Aufgabenteil a beschriebene Sprache L(G) lässt sich sehr gut nachvollziehen. Umso schwerer tue ich mir mit der formalen Beschreibung. Gibt es die Möglichkeit, einer kurzen Erläuterung?

LG und vielen Dank!

Answer 1

Sie meinen diese Formulierung, oder?

$$L(G) = \{\underbrace{v_0xv'_0}_{A} \cdot \prod_{i=1}^n
\mbox{+}\underbrace{v_ixv'_i}_{A} \ | \ n \in \mathbb{N}_0 \mbox{ und } \forall i \in \{0, \ldots, n\} : v_i \in \{a, b\}^\star\}$$

Das ist so zu lesen: Zunächst bezeichnet ein Apostroph die Rückwärtsschreibung eines Strings (bspw. ist $(ababb)' = bbaba$. Das große $\prod$ bezeichnet die mehrfache Hintereinanderschreibung von Strings - wie die Summe in der Arithmetik durch das Große $\sum$-Symbol bezeichnet wird (oder eben die Multiplikation auch durch das große $\prod$).

Also haben wir hier Wörter, die eine $n+1$-fache Hintereinanderschreibung von $v_ixv'_i$ darstellen ($n+1$, weil es mit $0$ vor dem $\prod$ losgeht; mindestens einmal "$vxv'$" kommt also auf jeden Fall vor - oder anders gesagt: das leere Wort ist nicht Teil der Sprache), verbunden mit einem "+". (Das "+" ist hier vielleicht die verwirrende Stelle: Es ist hier tatsächlich ein Zeichen des der Sprache zugrunde liegenden Alphabets und kein Rechensymbol!) Die $v_i$ sind beliebige Wörter über $\{a, b\}$, wie der Teil nach dem $|$ zeigt. $x$ ist und bleibt $x$, und danach kommt das jeweilige $v_i$ nochmal rückwärts geschrieben. Dadurch ergibt sich genau die Sprache, wie auch im Fließtext beschrieben.