Schnittmenge von Sprachen: Ist die Sprache L1 n L2 regulär?

Question

Gegeben sind zwei reguläre Sprachen L1 und L2. Man zeige oder widerlege, dass der Schnitt L1 n L2 regulär ist.

Wie soll das gehen?

Comments

https://www.google.de/search?q=schnitt+regulaerer+sprachen

Erster Treffer:

http://www.iti.fh-flensburg.de/lang/theor/regulaer-abgeschlossen.htm

Das muesste man als Informatiker selber hinkriegen ...

---

Danke, aber den Link kannte icj schon.

---

Ich nehme an, das soll heissen: "Danke, aber ich kann damit nichts anfangen." Das ist sehr verdaechtig, denn die Argumentation dort ist ganz einfach und kurz. In jedem Falle simpler als die Antwort.

Answer 1

Verwende das kartesische Produkt der beiden Zustandsmengen als neue Zustandsmenge.

Zustandsübergange von (xn, ym) nach (xp, yq) beim Lesen von a gibt es, wenn man mittels a von xn nach xp im einen und von ym nach yq im anderen Automaten konnte.

Lass dir noch was wegen der Endzustände einfallen.