Hallo zusammen,
kann mir jmd helfen wie man beweisen kann, dass die kontextfreien Sprachen gegenüber Verkettung abgeschlossen sind und gegenüber Hüllenbildung…
WÄren nett wenn mir jmd helfen kann.
'n Abend.
(1) Verkettung.
Betrachte die KFS LA und LB. Jede dieser beiden Sprachen kann durch eine kontextfreie Grammatik beschrieben werden. Sorge dafür, dass die Nonterminale beider Grammatiken disjunkt sind. Vereinige beide Grammatiken. Sei SA das Startsymbol der Grammatik, die LA erzeugt und sei SB das Startsymbol der Grammatik, die LB erzeugt. Füge ein neues Startsymbol S hinzu, dass in beiden Grammatiken nicht vorkommt, sowie die Regel S → SASB. Ist die so entstandene Grammatik kontexfrei? Welche Sprache erzeugt sie?
(2) Hüllenbildung.
Zeige analog zu (1), dass KFS unter Vereinigung abgeschlossen sind. (Wie muss dann die Regel für das neue Startsymbol aussehen?) Dann mit vollständiger Induktion und unter Verwendung von (1) zeigen, dass Ln für n ≥ 0 kontexfrei ist, wenn L es ist. Wegen der Abgeschlossenheit unter Vereinigung ist dann auch … na?
Gruß,
Ralf