Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in KON-AA

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

Mon, 03 Feb 2020 12:21:26 +0000

Danke für die Klarstellung

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.

Kommentar bearbeitet: ist Musterlösung eine kontextsensitive Grammatik?

Fri, 26 Dec 2014 17:18:16 +0000

$1S0 \rightarrow 1A$ ist NICHT kontextsensitiv und auch nicht monoton. $1S \rightarrow 1A$ ist kontextsensitiv, aber $S1 \rightarrow 1A$ ist nicht kontextsensitiv (aber monoton).

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)

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

Wed, 26 Nov 2014 13:59:22 +0000

Deine Aussage ist eine richtige Folgerung aus der Definition der Grammatik. Daraus ergibt sich aber keine Notwendigkeit $j\in \mathbb{N}$ in der Definition der Grammatik zu schreiben, da beide Versionen dasselbe ausdrücken würden.

Sven (Tutor)

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)