---

Geschrieben von Pampelmuse am 28.04.2007 um 15:52:

  Reguläre Sprachen Beweis

Hallo,

hab folgendes Problem , komme nicht weiter bzw. hab keine Idee

Beweisen Sie, dass die Klasse der regulären Sprachen unter den Operationen Durschnitt und Komplement abgeschlossen ist.
Gibt es noch andere Operationen, unter denen REG abgeschlossen ist?

---

Geschrieben von Tobias am 28.04.2007 um 18:12:

 

Welche Sprachen sind denn regulär?

---

Geschrieben von Pampelmuse am 29.04.2007 um 09:17:

 

Hi,
rechtslineare und linkslineare Grammatiken =>
G = {Sum,N, P, S}

A->wB
oder
A->Bw
oder
C->epsilon

wobei A, B und C Nichtterminalsymbole aus N und w ein Terminal aus Sum ist.

---

Geschrieben von Tobias am 29.04.2007 um 09:36:

 

Und was ist mit Automaten?

---

Geschrieben von Pampelmuse am 29.04.2007 um 09:41:

 

Muß ein
endlicher Automat sein,diese akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)

---

Geschrieben von ed209 am 29.04.2007 um 10:25:

 

Ist klar, was du zeigen mußt? Also was es bedeutet, daß eine Sprache unter dem Durchschnitt (bzw. dem Komplement) abgeschlossen ist.

---

Geschrieben von Pampelmuse am 29.04.2007 um 10:40:

 

Nein, ich denke mir aber das ich es irgendwie mit der Assoziativät Zeigen soll.

---

Geschrieben von Tobias am 29.04.2007 um 11:57:

 

Also ich glaube ich muss konkreter werden:

Wenn reguläre Sprachen mit endlichen deterministischen Automaten beschrieben werden können dann könntest du z.B. veruschen, für eine beliebige reguläre Sprachen einen Automat zu konstruieren, der das Komplement beschreibt. Warum wäre das schon ein Beweis für die Abgeschlossenheit unter Komplementbildung?

---

Geschrieben von ed209 am 29.04.2007 um 11:58:

 

Eine Menge M von Mengen sind unter dem Durchschnitt abgeschlossen wenn für jede Menge und gilt .

---

Geschrieben von Pampelmuse am 29.04.2007 um 13:59:

 

OK zunächst mal die Vereinigung:

Zitat:

Original von ed209 Sei und

mit
A=(a_1,a_2,...,a_n) regulär und B=(b_1,b_2,...,b_n) regulär
=>
(a_1,a_2,...,a_n) |(b_1,b_2,...,b_n) sind regulär
=>
(a_1,a_2,...,a_n) Schnitt(b_1,b_2,...,b_n) sind regulär
=>
A Schnitt B regulär und element M

---

Geschrieben von Tobias am 29.04.2007 um 15:00:

 

Hä?

Was ist denn da was? Was soll (a_1,a_2,...,a_n) sein? Wie kommst du von "|" (das soll wohl oder sein) auf "Schnitt"?

---

Geschrieben von Pampelmuse am 29.04.2007 um 19:35:

 

Danke erstmal.