Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in KON-AA

Beantwortet: 10 Kontextfreie Grammatik Teil 2 Folie GDI2 -107 (Pumping-Lemma für kontextfreie Sprachen)

Mon, 03 Feb 2020 10:19:06 +0000

Hallo,

ja da hast du recht das ist in den Folien nicht korrekt. Hier wird immer wieder abwechselnd z und w vertauscht auch innerhalb einer Aufgabe. Ich gebe es mal an die Übungsleiter weiter. Ursprünglich wollte man hier w weiterhin für das wort stehen lassen (da es vorher auch immer so war) und hat deshalb bei uvwxy dass w durch z ersetzt dies aber anscheinand an manchen Stellen vergessen.

Constantin (Tutor)

Beantwortet: Algorithmus Grammatik zu Kellerautomat

Mon, 13 Jan 2020 14:59:49 +0000

Hallo,

laut Algorithmus benötigen wir 3 Zustände. Zuerst fügen wir unser Startsymbol in den Keller ein und wechseln in den Zustand s1. Dann wird für jede Regel der Grammatik ein lambda-Übergang in s1 definiert sowie die Lösch-Vorgänge. Der letzte Schritt ist ein lambda-Übergang in den Endzustand.

Hoffe das hilft dir weiter

Viele Grüße

Jara (Tutorin)

Beantwortet: Ableiten von Wörtern bei Grammatiken in Chomsky-Normalform

Fri, 12 Jan 2018 07:50:15 +0000

Hallo,

Zur ersten Frage:

Eine CNF besitzt eine sehr eingeschränkte Regelmenge, d.h. Ableitungsmöglichkeiten, da lediglich erlaubt ist: N -> NN | T. Damit erhält man ein etwas sequentielleres und strukturierteres Vorgehen beim Ableiten eines Testworts.

Im Gegensatz dazu sind bei beispielsweise Kontextfreien Grammatiken (aus denen oft eine CNF abgeleitet wird) die Ableitungen von einem N beliebig. Daher können diese sehr unschön aussehen, müssen allerdings nicht.

Im Allgemeinen ist es daher sinnvoll von einer CNF auszugehen. Ist die ursprüngliche Grammatik aber direkt einleuchtend, kann auch diese verwendet werden.

Zur zweiten Frage:

Nein gibt es leider nicht. Es ist aber immer sinnvoll, sich vorab eine grobe Struktur zu überlegen, über welche Schritte das Testwort erreicht werden kann.

Viele Grüße,

Timon (Tutor)

Beantwortet: Muss man in CNF/GNF umformen können?

Thu, 09 Feb 2017 14:24:09 +0000

Nur CNF, nicht GNF.

Beantwortet: ist Musterlösung eine kontextsensitive Grammatik?

Wed, 26 Nov 2014 14:12:41 +0000

Das ist genau richtig, eine kontextfreie Grammatik hat nur ein Nonterminalsymbol auf der linken Seite (so wie in der Musterlösung), genauer:

$N \times (N \cup T)^\star$

Eine kontextsensitive Grammatik kann auf der linken Seite noch einen Kontext haben

$\phi_1A\phi_2 \rightarrow \phi_1 \psi \phi_2$ mit $\phi_1,\phi_2, \psi \in (N\cup T)^\star, A \in N, \psi \neq \lambda$

Sie sollten bei Ihrer Grammatik auch noch $A \rightarrow \lambda$ einfügen, sonst erhalten Sie immer mindestens doppelt so viele einsen wie nullen, und können so nicht alle geforderten Wörter erzeugen. Beachten Sie bitte auch, dass Sie bei den Terminal- und Nonterminalmengen Mengenklammern verwenden und die Produktion ebenfalls so angeben.

Freundliche Grüße
Friederike Pfeiffer

Beantwortet: Testwort 10101 zulässig ?

Wed, 26 Nov 2014 14:08:50 +0000

$ 0^i1^j$ heißt, dass erst ALLE 0er kommen müssen und dann ALLE 1er. 10101 ist daher nicht in der Sprache enthalten und lässt sich folglich auch nicht mit der Musterlösung erzeugen. Du verwechselst $0^i$ (i Nullen hintereinander) wahrscheinlich mit der Schreibweise $|w|_0$ für die Anzahl der 0er in w, egal wo sie in w stehen.

Tobias (Tutor)

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Wed, 26 Nov 2014 13:54:55 +0000

Ist diese Lösung auch richtig:

S --> 0SA / A,

A --> AA / 1

Danke schonmal,

Grüße Melanie

Beantwortet: Allgemeine Vorgehensweise für diesen Aufgabentyp

Wed, 26 Nov 2014 13:39:34 +0000

Zur Vorgehensweise bei solchen Aufgaben:

Eine allgemeines Schema gibt es da nicht. Vor allem bei rechtslinearen Grammatiken kann man mit den Nonterminalsymbolen bestimmte Situationen codieren. Bei kontextfreien Grammatiken hat man oft die Struktur N -> TNT, um gleich viele (u.U.) verschiedene Terminalsymbole zu erzeugen. Dann kann man dieses Nonterminalsymbol N noch auf andere Zeichen abbilden, um weitere Eigenschaften zu realisieren. Üben um Erfahrung zu sammeln hilft hier viel ;-)

Viele Grüße,

Sven (Tutor)