Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2013-N-03

Beantwortet: neues Nonterminal S' zwingend notwendig?

Thu, 18 Mar 2021 17:20:27 +0000

Hallo,

die Einführung von S' ist zwingend der erste Schritt der Überführung in CNF, wenn es einen Lambda-Übergang von S gibt und S auf einer der rechten Seiten vorkommt.

Schau dir am besten nochmal die Definition einer Chomsky Normalform an. Zur Überführung in diese gibt es auch sehr gute Videos auf dem YouTube Kanal von "nLogSpace".

Beste Grüße,

Martin (Tutor)

Beantwortet: CNF- JA oder NEIN?

Thu, 06 Feb 2020 11:31:59 +0000

In Tutorium 4 steht es eindeutig.

Einfach gesagt sind folgende Regeln erlaubt:

1.Von Nonterminalsymbolzu 2 Nonterminalsymbolen
2.Von Nonterminalsymbolzu 1 Terminalsymbol

Also muss die Grammatik Lambda frei sein abgesehen von Startsymbol zu Lambda, dies ist aber nur möglich wenn Startsymbol nicht auf der rechten Seite vorkommt.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: CNF akzeptiert doch das leere Wort garnicht?

Sat, 10 Feb 2018 18:58:47 +0000

Um eine Grammatik in CNF zu überführen, muss man sie zunächst $\lambda$-frei machen. Deshalb wird in der Aufgabe der neue Startzustand S' eingeführt, von dem aus ein $\lambda$-Übergang erlaubt ist.

Viele Grüße
Julia (Tutor)

Beantwortet: S' -> S entspricht nicht der CNF

Sun, 14 Feb 2016 10:32:28 +0000

Laut 3-32 gilt für Schritt 4 folgendes : Ersetze jede Regel der Form A-> B1...Bn

mit n >=3 . und das würde ja auf S-> S´ nicht zutreffen , da hier nur n=1 gilt .

Beantwortet: Müsste man die Umbennung nicht im 2. Schritt eliminieren?

Wed, 23 Sep 2015 14:32:24 +0000

Hallo,

Eine reine Umbenennung wäre es, wenn man von S' nicht auch auf das leere Wort kommen könnte. Da S' somit auf keiner rechten Seite mehr stehen darf kann dies nicht eliminiert werden.

Viele Grüße,

Janina (Tutorin)