Fragen zu Abschlusseigenschaften

Question

Frage:

Überlegen sie sich, ob folgende Aussagen für beliebige Sprachen L1, L2 ⊆ ∑* gelten. Geben Sie jeweils entweder einen Beweis oder ein Gegenbeispiel an.

1. Wenn L1 U L2 regulär ist, dann ist mindestens eine der Sprachen L1 oder L2 regulär.

2. Wenn L1 U L2 regulär und L2 endlich ist, dann ist auch L1 regulär.

3. Wenn L1 U L2 nicht regulär ist, dann ist mindestens eine der Sprachen L1 oder L2 nicht regulär.

Usw.

Ich verstehe leider nicht, wie man so etwas nachweisen kann. Muss man dazu Automaten bilden, und schauen was dann bei der Vereinigung zweier Automaten( ein Automat ist endlich der andere nicht, bzw. Regulär) und schauen ob es ein regulärer Automat bei einem regulären vereinigt mit einen unregulären Automaten ein regulärer oder unregulärer Automat entsteht, oder wie kann man das mit Gegenbeispielen oder beweisen belegen ?

Ich bräuchte quasi zumindest denn Anhaltspunkt, wie man hierbei vorgehen sollte.

Danke schonmal im Voraus für Ihre Antworten.

Answer 1

1. Wenn L1 U L2 regulär ist, dann ist mindestens eine der Sprachen L1 oder L2 regulär.

Zunächst ein mal solltest du dich entscheiden, ob du die Aussage

• Für jedes L1 und jedes L2 gilt: wenn L1 U L2 regulär ist, dann ist mindestens eine der Sprachen L1 oder L2 regulär.

oder die Aussage

• Es gibt L1 und L2 so dass gilt: L1 U L2 ist regulär aber weder L1 noch L2 sind regulär.

beweisen möchtest.

Nur eine dieser beiden Aussagen wird sich beweisen lassen, weil die ein Aussage die Negation der anderen Aussage ist.

Nachdem du dich für eine der Aussagen entschieden hast versuchst du, diese Aussage zu beweisen. Das machst du dann so lange, bis du entweder die Aussage bewiesen hast, oder zu der Überzeugung gekommen bist, dass wohl doch die andere Aussage wahr ist.

Tipp: ∑*  ist regulär.