Vereinigung nicht-regulärer Sprachen
-
Hallo.
Eine Aufgabe lautet:
Gegeben seien zwei nicht-reguläre Sprachen L1 und L2.
Dann ist L1υL2 immer ebenfalls nicht-regulär.
Beweisen oder widerlegen Sie!Ich glaube, daß es nicht immer so ist und versuche, ein Gegenbeispiel zu finden - wo also die Vereinigung von zwei nicht-regulären Sprachen regulär ist.
Klassisches Beispiel für eine nicht-reguläre Sprache ist ja {anbn | n≥0}.
Meine Idee wäre, diese nicht-reguläre Sprache mit ihrem Komplement bezüglich {aibj | i,j≥0} zu vereinigen. Das Komplement zu dieser Sprache müsste doch sein: {aib^j | i,j[e]ge[/e]0, i[e]ne[/e]j}, also alle Wörter, bei denen zuerst nur a's kommen und danach eine davon verschiedene Anzahl b's.
Wenn ich das richtig sehe, ist diese Sprache nicht-regulär.Die Vereinigung ist dann wieder {a[h]ibj^ | i,j≥0}, und diese Sprache ist regulär, weil man die Wörter z.B. durch den regulären Ausdruck (a)(b) darstellen kann.
Liege ich da richtig?
-
Sorry, die Formatierung ging kaputt!
Hallo.
Eine Aufgabe lautet:
Gegeben seien zwei nicht-reguläre Sprachen L1 und L2.
Dann ist L1υL2 immer ebenfalls nicht-regulär.
Beweisen oder widerlegen Sie!Ich glaube, daß es nicht immer so ist und versuche, ein Gegenbeispiel zu finden - wo also die Vereinigung von zwei nicht-regulären Sprachen regulär ist.
Klassisches Beispiel für eine nicht-reguläre Sprache ist ja {anbn | n≥0}.
Meine Idee wäre, diese nicht-reguläre Sprache mit ihrem Komplement bezüglich {aibj | i,j≥0} zu vereinigen. Das Komplement zu dieser Sprache müsste doch sein: {aibj | i,j≥0, i≠j}, also alle Wörter, bei denen zuerst nur a's kommen und danach eine davon verschiedene Anzahl b's.
Wenn ich das richtig sehe, ist diese Sprache nicht-regulär.Die Vereinigung ist dann wieder {aibj | i,j≥0}, und diese Sprache ist regulär, weil man die Wörter z.B. durch den regulären Ausdruck (a)(b) darstellen kann.
Liege ich da richtig?
-
Die Komplementbildung ist nicht ganz richtig (zum Komplement deiner Beispielsprache gehören auch alle Wörter, die sich überhaupt nicht in das aibj-Schema einordnen lassen können (z.B. "baaabba") - aber das Endergebnis ist richtig: Wenn du die (nicht-reguläre) Sprache L mit ihrem Komplement ~L (auch nicht-regulär) vereinigst, erhältst du die Sprache ∑* (und die ist regulär).
-
CStoll schrieb:
Die Komplementbildung ist nicht ganz richtig
Doch, ich hab ja geschrieben: Komplement bezüglich {aibj}, also nicht bezüglich ∑*.