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

neues Nonterminal S' zwingend notwendig?

Wed, 17 Mar 2021 22:18:26 +0000

Hallo,

muss man bei der Umwandlung in CNF zwingend das neue Startsymbol S' einfügen (wenn S nach lambda abgeleitet wird)? Oder ist das nur "Zusatz" ?

Vermutlich hat es auch damit was zu tun, dass man sonst gar nicht mehr das leere Wort ableiten kann..?

Beste Grüße

CNF- JA oder NEIN?

Thu, 06 Feb 2020 11:21:19 +0000

Hallo zusammen,

zu dieser Aufgabe gibt es bereits 3 Threads, jedoch findet man keinen gemeinsamen Konsens:

Ist in der CNF nun ein Lambda erlaubt oder nicht?

- Nach der VL (Foliensatz 10, Folie 73) steht geschrieben: "Sprache darf nicht leeres Wort enthalten bzw. keine Regel Sg -> Lambda"

- Die Musterlösung gibt in der ersten Produktionszeile ein Lambda an und hat sogar nur ein Nonterminalzeichen auf der rechten Seite.

- Ein Thread behauptet zudem folgendes:

https://info2.aifb.kit.edu/qa/index.php?qa=6408&qa_1=cnf-akzeptiert-doch-das-leere-wort-garnicht

Wo steht in unseren VL-Folien geschrieben, dass in der ersten Zeile ein Übergang zu Lambda erlaubt sei?

Um aufklärende Mithilfe wäre ich dankbar.

CNF akzeptiert doch das leere Wort garnicht?

Sat, 10 Feb 2018 18:23:36 +0000

Hallo
Im Vorlesungsskript steht doch das man immer nur eine äquivalente Grammatik angeben kann die aber las leere Wort nicht akzeptiert, da dies dann keine CNF mehr wäre. Wieso wird hier dann doch so vorgegangen ?
Lg un danke

S' -> S entspricht nicht der CNF

Sun, 14 Feb 2016 08:13:21 +0000

Hallo,

ich bin gerade über die Lösung zu dieser Aufgabe gestolpert.

Die Überführung S' -> S entspricht nicht der Chomsky-Normalform, da sich auf der rechten Seite keine zwei Nonterminalsymbole befinden oder sehe ich das falsch?

Siehe Bild inklusive Lösungsvorschlag.

LG urdsc

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

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

Durch S' -> S in der endgültigen Lösung habe ich doch noch eine reine Umbenennung, die ich im zweiten Schritt hätte eliminieren müssen, oder nicht?

Vielen Dank für eine Antwort