Reguläre Sprachen über Alphabet

Question

Seien L1, L2 reguläre Sprachen und L3 eine kontextfreie Sprache über dem Alphabet ∑. Welche der folgenden Aussagen ist im allgemeinen wahr?
a) L3 ∪ ∑* ist nicht regulär
b) L1 \ L2 ist regulär
c) L1 \ L2 ist nicht regulär
d) L3 ∩ L1 ist regulär

Ich komme ganz gut mit Sprachen und Alphabeten im Praktischen Anwendungsfall klar aber bei solchen allgemeinen Fragen hapert es, könnte mir jemand erklären was hier die korrekt Antwort wäre und wieso?

Comments

Aloha :)

Das ist eine Frage für die Theoretische Informatik und gehört daher in die Stacklounge...

Reguläre Sprachen bestehen aus Regeln der Form:$$A\to a\quad;\quad A\to aB$$Eine Variable \(A\) wird auf ein Terminal \(a\) abgebildet oder auf ein Terminal \(a\) gefolgt von einer einzigen weiteren Variablen \(B\).

Bei kontextfreien Sprachen steht links weiterhin eine einzelne Variable (daher "kontextfrei"), die aber auf eine beliebige Folge von Terminalen und / oder Variablen abgebildet werden kann, etwa so:$$A\to aBAB\quad;\quad A\to ccBAaBc$$

Vielleicht reicht dir das schon, um deine Fragen zu beantworten?

Ansonsten warte am besten auf die Experten aus der Stacklounge.

---

Theoretische Informatik ist Mathematik.

---

Physik ist auch Mathematik.

---

Nein, Physik ist viel mehr als Rumhantieren mit mathematischen Strukturen. Theoretische Informatik ist nur Rumhantieren mit mathematischen Strukturen.

---

Für Physik gibt es ein eigenes Forum und für Informatik auch. Wirtschaftsfragen werden hingegen im Mathe-Forum zugelassen.

Das mach meiner Meinung nach zwar keinen Sinn, weil die MINT-Fächer sehr eng miteinander verhzahnt sind, aber so ist es nun mal ;)

Answer 1

a) L3 ∪ ∑* ist nicht regulär

Um das zu beurteilen reicht Mengenlehre.

b) L1 \ L2 ist regulär

Verwende Automaten um die Sprache darzustellen.

c) L1 \ L2 ist nicht regulär

Verwende Automaten um die Sprache darzustellen.

d) L3 ∩ L1 ist regulär

Um das zu beurteilen reicht Mengenlehre.