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

Beschreibung L2

Wed, 16 Jan 2019 09:52:48 +0000

Hallo,

in der Lösung steht zur L2, dass |w| größer gleich 2 sein muss.

Wieso ist dies der Fall? Die Grammatik kann doch auch Wörter produzieren, die nur ein Zeichen lang sind?

Beantwortet: Tut 2 Auf 8b

Wed, 19 Jul 2017 17:49:27 +0000

Das ist nicht nötig. Entscheidend ist der Allquantor. $uabv$ steht für alle möglichen Zerlegungen von $w$. Daher muss die Bedingung für alle Zerlegungen $uabv$ von $w$ gelten.

Beantwortet: Müsste die GNF nicht λ-frei sein?

Mon, 21 Sep 2015 09:22:25 +0000

Hallo,

das ist so nicht richtig. Die GNF darf auf das leere Wort abbilden (vgl. Vorlesungsfolie 3-34). In dieser Vorschrift steht, dass phi ein Element von N* sein muss und N* bedeutet beliebig viele Nonterminalsymbole, da ist die 0 mit dabei.

Die rechtslineare Grammatik darf nicht auf das leere Wort abbilden. Das heißt aber nicht, dass es keine Nonterminale geben darf, die auf das leere Wort abbilden. Wenn du dir die Grammatik noch einmal anschaust merkst du, dass jedes S auf ein Terminal- und ein Nonterminalsymbol abbildet, das leere Wort kann also nicht produziert werden. Eine Vorschrift

S --> lamda

würde dieser Vorschrift widersprechen und daher wäre das keine rechtslineare Grammatik. Da das leere Wort nicht abgebildet werden kann, ist dieses Kriterium jedoch erfüllt.

Max (Tutor)

Beantwortet: Werden Wörter der Länge 1 akzeptiert?

Mon, 21 Sep 2015 09:21:17 +0000

Hallo,

mithilfe der Grammatik können folgende Wörter generiert werden:

Wörter der Länge 1: 0, 1, 2

Wörter der Länge >= 2, in denen keine zwei gleichen Zeichen aufeinander folgen.

Ich sehe keine Stelle, an der das im Widerspruch zu der Lösung stehen würde. Bitte nennen Sie mir die Stelle, die Sie meinen.

Viele Grüße

Irina (Tutorin)

Beantwortet: L2: fehlende Beschränkung?

Mon, 21 Sep 2015 09:18:10 +0000

Hallo,

nein so eine Beschränkung ist nicht nötig, denn $ w = uabv \Rightarrow a \neq b $ muss für alle ( $ \forall$ ) mögliche u und v gelten.

Das Wort 0012 ist nicht Teil der Sprache, weil die Partition $ u=\varnothing , a=0, b=0, v = 12$ nicht zugelassen ist.

Damit ein Wort Teil der Sprache ist, muss es für alle mögliche Partitionen die Bedingungen erfüllen, dank der Allquantor $ \forall $.

Grüße

Antonio (Tutor)