regulaeren Sprachen abgeschlossen unter unendl. Vereinigung

[Johannes Lichtenberger]

Hallo,

wäre folgender Beweis, dass die Klasse der regulären Sprachen
abgeschlossen ist unter unendlicher Vereinigung korrekt?

Jede reguläre Sprache kann durch einen regulären Ausdruck beschrieben
werden. 2 reg. Sprachen werden durch Vereinigung (+) ihrer regulären
Ausdrücke vereinigt. Hierbei entsteht wieder ein regulärer Ausdruck
(abgeschlossen). Somit kann man die neu erzeugte Sprache wieder mit
einer anderen vereinigen.

=> die unendliche Vereinigung über alle regulären Sprachen ist somit
abgeschlossen.

Unendliche Vereinigung heist doch hier, reguläre Sprachen unendlich oft
miteinander vereinigt!?

Viele Grüsse,
Johannes

[Marc Spisländer]

Post by Johannes Lichtenberger
wäre folgender Beweis, dass die Klasse der regulären Sprachen
abgeschlossen ist unter unendlicher Vereinigung korrekt?
Jede reguläre Sprache kann durch einen regulären Ausdruck beschrieben
werden. 2 reg. Sprachen werden durch Vereinigung (+) ihrer regulären
Ausdrücke vereinigt. Hierbei entsteht wieder ein regulärer Ausdruck
(abgeschlossen). Somit kann man die neu erzeugte Sprache wieder mit
einer anderen vereinigen.
=> die unendliche Vereinigung über alle regulären Sprachen ist somit
abgeschlossen.
Unendliche Vereinigung heist doch hier, reguläre Sprachen unendlich oft
miteinander vereinigt!?

Die Argumentation ist leider falsch. Betrachte für alle k aus N die
folgenden Sprachen:

L_k := {a^k b^k}

Dann gilt für alle k: L_k ist regulär, weil L_k nur ein Wort enthält. Die
unendliche Vereinigung dieser Sprachen ist die Sprache

L = {a^n b^n : n aus N},

die nicht regulär ist. Das kann man mit dem Pumping-Lemma beweisen.

Tschüss
Marc

[Johannes Lichtenberger]

Post by Marc Spisländer

Post by Johannes Lichtenberger
wäre folgender Beweis, dass die Klasse der regulären Sprachen
abgeschlossen ist unter unendlicher Vereinigung korrekt?
Jede reguläre Sprache kann durch einen regulären Ausdruck beschrieben
werden. 2 reg. Sprachen werden durch Vereinigung (+) ihrer regulären
Ausdrücke vereinigt. Hierbei entsteht wieder ein regulärer Ausdruck
(abgeschlossen). Somit kann man die neu erzeugte Sprache wieder mit
einer anderen vereinigen.
=> die unendliche Vereinigung über alle regulären Sprachen ist somit
abgeschlossen.
Unendliche Vereinigung heist doch hier, reguläre Sprachen unendlich
oft miteinander vereinigt!?

Die Argumentation ist leider falsch. Betrachte für alle k aus N die
L_k := {a^k b^k}
Dann gilt für alle k: L_k ist regulär, weil L_k nur ein Wort enthält.

Endliche Sprachen kann man mittels regulären Ausdrücken w1+...+wn
ausdrücken bzw. werden natürlich durch einen EA erkannt, haben
endlichen Index bzgl. der Nerode Relation. Zudem lässt es sich durch
das PL zeigen.

(hoffentlich richtig und alle Möglichkeiten mit einbezogen, wobei man
die Einhaltung der Eigenschaften natürlich noch beweisen muss).

Post by Marc Spisländer
Die unendliche Vereinigung dieser Sprachen ist die Sprache
L = {a^n b^n : n aus N},
die nicht regulär ist. Das kann man mit dem Pumping-Lemma beweisen.

Für ein beliebiges n > 0 sei w = a^n b^n. Dann ist |w| > n und für jede
Darstellung w = uvx mit |uv| <= n und |v| >= 1 ist v = a^k mit k >=
1. Für uv^0x = a^n-k b^n ist das so erzeugte Wort nicht mehr Element
der Sprache (hmm, ok, n aus N0).

Für n aus N ist es allerdings bei Wikipedia beschrieben.

Wenn |uv| = n ist, müsste dann x = das leere Wort Epsilon sein, oder?
(generell auf das PL bezogen).

Hm, dann habe ich es nur für endliche Vereinigung nachgewiesen.

Wie kann ich dann zeigen, dass die Klasse der Regulären Sprachen unter
unendlicher Vereinigung abgeschlossen ist, wenn ich somit nichteinmal
zeigen konnte, dass endliche Sprachen unter unendlicher Vereinigung
wieder regulär sind?

Viele Grüsse,
Johannes

[Sebastian Biallas]

Post by Johannes Lichtenberger
Wie kann ich dann zeigen, dass die Klasse der Regulären Sprachen unter
unendlicher Vereinigung abgeschlossen ist,

Gar nicht.

[Marc Spisländer]

Hallo Johannes,

Post by Johannes Lichtenberger
Wie kann ich dann zeigen, dass die Klasse der Regulären Sprachen unter
unendlicher Vereinigung abgeschlossen ist, wenn ich somit nichteinmal
zeigen konnte, dass endliche Sprachen unter unendlicher Vereinigung
wieder regulär sind?

Naja, ich dachte, meine Antwort hätte deine Frage beantwortet.

Abgeschlossenheit unter unendliche Vereinigung bedeutet doch, dass, wenn ich
unendlich viele reguläre Sprachen vereinige, ich auf jeden Fall wieder eine
reguläre Sprache erhalte. Mein Gegenbeispiel zeigte, dass die regulären
Sprachen *nicht* abgeschlossen sind unter unendl. Vereinigung. Ich habe
unendlich viele reg. Sprachen vereinigt und gezeigt, dass die Vereinigung
keine reg. Sprache mehr ist.

Grüße,
Marc

[Johannes Lichtenberger]

Post by Marc Spisländer
Hallo Johannes,

Post by Johannes Lichtenberger
Wie kann ich dann zeigen, dass die Klasse der Regulären Sprachen unter
unendlicher Vereinigung abgeschlossen ist, wenn ich somit nichteinmal
zeigen konnte, dass endliche Sprachen unter unendlicher Vereinigung
wieder regulär sind?

Naja, ich dachte, meine Antwort hätte deine Frage beantwortet.

Ach, klar, ich dachte irgendwo gelesen zu haben, dass reguläre Sprachen
unter unendlicher Vereinigung abgeschlossen wären, war aber wohl eher
die endliche Vereinigung, dankeschön :-)

Viele Grüsse,
Johannes

[Stefan Kirchner]

Post by Johannes Lichtenberger
Hallo,
wäre folgender Beweis, dass die Klasse der regulären Sprachen
abgeschlossen ist unter unendlicher Vereinigung korrekt?

Nein.

Post by Johannes Lichtenberger
Jede reguläre Sprache kann durch einen regulären Ausdruck beschrieben
werden. 2 reg. Sprachen werden durch Vereinigung (+) ihrer regulären
Ausdrücke vereinigt. Hierbei entsteht wieder ein regulärer Ausdruck
(abgeschlossen). Somit kann man die neu erzeugte Sprache wieder mit
einer anderen vereinigen.

Das stimmt.

Post by Johannes Lichtenberger
=> die unendliche Vereinigung über alle regulären Sprachen ist somit
abgeschlossen.

Nein, mit diesem Argument hast Du nur gezeigt, daß die Vereinigung
_endlich_ vieler regulärer Sprachen regulär ist.

Als Gegenbeispiel zu Deinem "Beweis" betrachte eine uneneinscheidbare
Sprache L={a_1, a_2,...}.

Dann kann die Sprache L_i = {a_i} durch einen regulären Ausdruck
beschrieben werden.

Die unendliche Vereinigung
oo
| |
| | L_i
\---/
i=1

ist dann gerade L und nach Voraussetzung unentscheidbar -- also
insbesondere nicht regulär.


Gruß Stefan

[Michael Mueller]

Hallo,

Post by Johannes Lichtenberger
wäre folgender Beweis, dass die Klasse der regulären Sprachen
abgeschlossen ist unter unendlicher Vereinigung korrekt?

Nein.

Da jede (unendliche) Sprache als eine unendliche Vereinigung von
regulaeren Sprachen dargestellt werden kann.

Beweis: Waehle als regulaere Sprachen einelementige Mengen.

Aus obiger Aussage wuerde also folgen, dass jede Sprache regulaer ist.

Michael Mueller