Hausübung 6

verklixt1
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 29. Dez 2007 20:22

Hausübung 6

Beitrag von verklixt1 »

H1 a)

Also bei der a sollen wir ja die Grammatik in Chomsky-Normalform bringen, jedoch ist dort eine E-Produktion(leeres Wort), dies wird doch im Skript ausgeschlossen.
Hab ich das falsch verstanden oder sollen wir die E-Produktion irgendwie rausnehmen???

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Hausübung 6

Beitrag von dschneid »

Ja, der Algorithmus zur Umwandlung einer kontextfreien Grammatik in die Chomsky-Normalform funktioniert nur mit Grammatiken ohne Epsilon-Produktionen. Es gilt aber auch mit Lemma 3.2.4, dass jede kontextfreie Grammatik in eine Grammatik ohne nicht-harmlose Epsilon-Produktionen umgewandelt werden kann. Das kannst du ja vorher einfach machen.

Antworten

Zurück zu „Archiv“