0 Daumen
133 Aufrufe

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.

von

1 Antwort

0 Daumen

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.

von 5,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community