Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

L(G) formale Darstellung

0 Punkte
36 Aufrufe
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!
Gefragt 14, Jan 2017 in AU-2-4 von Anonym  

Eine Antwort

0 Punkte
 
Beste Antwort

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.

Beantwortet 15, Jan 2017 von Lukas König Dozent (10,065,100 Punkte)  
Bearbeitet 15, Jan 2017 von Lukas König
...