Zeigen Sie L_{1} \cup L_{2} ist kontextfrei.

Question

Bitte um Hilfe bei folgender Aufgabe:

Es seien \( L_{1} \subseteq A^{*} \) und \( L_{2} \subseteq A^{*} \) zwei kontextfreie Sprachen über einem Alphabet \( A \). Zeigen oder widerlegen Sie die folgenden Aussagen:

a) \( L_{1} \cup L_{2} \) ist kontextfrei.

b) \( L_{1} \cap L_{2} \) ist kontextfrei.

Answer 1

a) Baue aus nichtdetministischen Kellerautomaten für \(L_1\) und \(L_2\) einen nichtdetministischen Kellerautomaten für \(L_1\cup L_2\)

b) Stelle eine bekanntermaßen nicht kontextfreie Sprache als Schnittmenge zweier kontextfreier Sprachen dar.