Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-2-4

Beantwortet: Welche Produktionsregeln sind zulässig für die Angabe einer rechtslinearen Grammatik?

Mon, 16 Dec 2019 09:52:21 +0000

Typ-3-Grammatik (rechtslineare Grammatik): (siehe VL. 8)

alle Produktionen von einer der Formen A → lamda, A → a oder A → aB mit a aus T und A, B aus N.

Rechtslinear: jeder Ableitungschritt höchstens ein Zeichen hinzukommt, Ableitung ausschliesslich nach rechts weitergehen kann

Die Produktion der Form S → 01S wäre somit für eine rechtslineare Grammatik nicht zulässig.

Viele Grüße

Jara (Tutor)

Beantwortet: Produktionsfunktion bei rechtslinearer Grammatik

Thu, 12 Dec 2019 19:26:52 +0000

Hallo,

da hier nur allgemein nach einer Grammatik und nicht nach einer vom Chomsky-Typ 3 (rechts- oder linkslinear) gefragt wurde ist es egal wie viele Non-/Terminalsymbole auf der rechten Seite steht.

LG

Constantin (Tutor)

Beantwortet: Produktzeichen an falscher Stelle

Tue, 29 Jan 2019 11:21:42 +0000

Hallo,

ich bin mir nicht ganz sicher, ob ich deine Frage richtig verstanden habe. Der kleine Punkt zeigt ja das Komplexprodukt (für "Hintereinanderschreiben") an und kann theoretisch sogar weggelassen werden, dient allerdings der Übersicht. Es ist als "und" zu verstehen, wohingegen das + als "oder" zu verstehen ist. Das Produktzeichen (großes Pi) ist einfach nur eine Kurzschreibweise, um mehrere Klomplexprodukte hintereinander zu schreiben.

Mit dem Produktzeichen hinter voxvo' zeigen wir also an, dass das, was danach kommt, einfach dahinter geschrieben werden kann, wobei das i hoch zählt. Wenn du einfach mal das Ganze ausschreibst, kommst du auf folgendes:

L(G) = v0xv0' + v1xv1' + v2xv2' + ... + vnxvn'

Ich hoffe, das hat beim Verständnis der Aufgabe geholfen.

Viele Grüße,

Nayeli (Tutorin)

Beantwortet: Striche beim Testwort

Thu, 04 Jan 2018 12:18:57 +0000

Hallo,

genau wie du vermutet hast: die Striche sollen eine Hilfestellung sein, welcher Teil von Wort im nächsten Schritt ersetzt wird (Strich über dem/den Zeichen) bzw. welcher Teil im Schritt davor ersetzt wurde (Strich unter dem/den Zeichen).

In der Prüfung kannst du diese natürlich angeben, wenn dir das hilft, ist aber nicht zwingend notwendig.

Gruß,

Maren (Tutorin)

Beantwortet: L(G) formale Darstellung

Sun, 15 Jan 2017 09:23:51 +0000

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: Alternativer Lösungsvorschlag (GNF)

Tue, 22 Sep 2015 09:56:27 +0000

Hallo,

von der Idee her nicht schlecht, leider stimmt es nicht ganz.

Gegenbeispiel:

S->aSA->aaSALSA->aaxALSA->aaxaLSA

->aaxa-SA->aaxa-xA->aaxa-xa

Dieses Wort kann erzeugt werden, leider ist es aber nicht Teil der Sprache. Leider ist das ganze nicht ganz einfach, da wir kein konkretes Verfahren kennen. Aber versuchs einfach nochmal :D

Gruß,

Adam (Tutor)

Beantwortet: Wie ergibt sich die Regelmenge?

Tue, 22 Sep 2015 09:54:41 +0000

Hallo,

1. Nicht alle Regeln werden benutzt, denn es ist nur die Erzeugung von einem möglichen Testwort. Allerdings kann die Grammatik an sich viele weitere Worte erzeugen.
2. Bedingungen einer Greibach Normalform:Die Greibach Normalform erlaubt nur Regeln der Form N->TN*. Also ein nicht Terminalsymbol zu einem Terminalsymbol und beliebig viele nicht Terminalsymbole (beliebig(*) viele kann auch null bedeuten)
3. Man kann sie nicht einfach weglassen, weil die für weitere Worte nötig sein könnten. Natürlich gibt es mehrere Lösungen, aber man kann die Regeln nicht einfach weglassen nur weil sie für die Erzeugung von einem bestimmten Testwort nicht benutzt werden
4. Das ist nicht in der Greibach Normalform, denn z.B S→A − S ist N→NTN und so eine Regel ist nicht erlaubt.
Man soll sich überlegen was bei einer Greibach Normalform erlaubt ist und dann die Regeln so umformen bis die die Bedingungen eine solche Form erfüllen.

Beste Grüße
Antonio (Tutor)