(Twitter)
0
Hallo user6d7173,
ich nehme mal an, es ist bekannt, dass \(V:=\{0^n1^n\;|\;n\in\mathbb{N}\}\) nicht regulär ist und $X:=\{0^n1^m\;|\;n,m\in\mathbb{N}\}$ regulär ist?
Angenommen $U$ wäre doch regulär. Zu zeigen ist ein Widerspruch.
Wegen der angenommenen Regularität von $U$ weißt du was über $X\setminus U=X\cap U^c$?
Was hat $X\setminus U$ mit $V$ zu tun?
Viele Grüße
Tobias
ich nehme mal an, es ist bekannt, dass \(V:=\{0^n1^n\;|\;n\in\mathbb{N}\}\) nicht regulär ist und $X:=\{0^n1^m\;|\;n,m\in\mathbb{N}\}$ regulär ist?
Angenommen $U$ wäre doch regulär. Zu zeigen ist ein Widerspruch.
Wegen der angenommenen Regularität von $U$ weißt du was über $X\setminus U=X\cap U^c$?
Was hat $X\setminus U$ mit $V$ zu tun?
Viele Grüße
Tobias
Diese Antwort melden
Link
geantwortet
tobit
Sonstiger Berufsstatus, Punkte: 275
Sonstiger Berufsstatus, Punkte: 275
Hallo user6d7173, dir auch ein gutes neues Jahr. Ich ergänze cauchys Kommentar:
Den entscheidenden Punkt hast du genannt: $X\setminus U$ ist (unter der Annahme $U$´wäre regulär) ebenfalls regulär. Mache dir nun anhand der konkreten Definitionen der Sprachen $X$, $U$ und $V$ die Beziehung $X\setminus U=V$ klar. Damit wäre also $V$ regulär im Widerspruch dazu, dass wir bereits wissen, dass $V$ nicht regulär ist.
Zur Frage, welche Mengenoperation hilft bzw. warum hier $X\setminus U$ und nicht $X\cap U$:
Ein zielführendes Vorgehen bei dieser Aufgabe, die Nicht-Regularität von $U$ zu zeigen ist somit folgendes: Wir nehmen an, $U$ wäre regulär und versuchen daraus mit den Abschlusseigenschaften zu schlussfolgern, dass dann eine weitere Sprachen regulär sein müsste, von der wir bereits wissen, dass sie nicht regulär ist.
Welche Mengenoperationen da hilfreich sind, hängt natürlich von der konkreten Definition von $U$ ab. Hier ist eine gewisse Kreativität gefragt. Im Zweifelsfall kann man auch mehrere Mengenoperationen probieren und schauen, ob eine zum Erfolg führt. Ziel ist, einen passenden Zusammenhang zwischen verschiedenen Sprachen (der Sprache, deren (Nicht-)Regularität noch unbekannt ist und Sprachen, deren (Nicht-)Regularität wir schon wissen) herzustellen.
Es ist im Rahmen der Lösungssuche keineswegs verboten, auch $X\cap U$ zu betrachten. Dann stellt man jedoch fest, dass hier $X\cap U=U$ gilt. Wir könnten also aus der (angenommenen) Regularität von $X$ und $U$ mit der Durchschnittsstabilität der regulären Sprachen nur auf die Regularität von $U$ schließen, was keine neue Information wäre. So sieht man , dass bei dieser (!) Aufgabe die Betrachtung von $X\cap U$ wohl nicht weiterhilft. Bei anderen Aufgaben könnte hingegen die Betrachtung von einem Durchschnitt sehr wohl hilfreich sein.
Viele Grüße, Tobias ─ tobit 02.01.2022 um 23:05
Den entscheidenden Punkt hast du genannt: $X\setminus U$ ist (unter der Annahme $U$´wäre regulär) ebenfalls regulär. Mache dir nun anhand der konkreten Definitionen der Sprachen $X$, $U$ und $V$ die Beziehung $X\setminus U=V$ klar. Damit wäre also $V$ regulär im Widerspruch dazu, dass wir bereits wissen, dass $V$ nicht regulär ist.
Zur Frage, welche Mengenoperation hilft bzw. warum hier $X\setminus U$ und nicht $X\cap U$:
Ein zielführendes Vorgehen bei dieser Aufgabe, die Nicht-Regularität von $U$ zu zeigen ist somit folgendes: Wir nehmen an, $U$ wäre regulär und versuchen daraus mit den Abschlusseigenschaften zu schlussfolgern, dass dann eine weitere Sprachen regulär sein müsste, von der wir bereits wissen, dass sie nicht regulär ist.
Welche Mengenoperationen da hilfreich sind, hängt natürlich von der konkreten Definition von $U$ ab. Hier ist eine gewisse Kreativität gefragt. Im Zweifelsfall kann man auch mehrere Mengenoperationen probieren und schauen, ob eine zum Erfolg führt. Ziel ist, einen passenden Zusammenhang zwischen verschiedenen Sprachen (der Sprache, deren (Nicht-)Regularität noch unbekannt ist und Sprachen, deren (Nicht-)Regularität wir schon wissen) herzustellen.
Es ist im Rahmen der Lösungssuche keineswegs verboten, auch $X\cap U$ zu betrachten. Dann stellt man jedoch fest, dass hier $X\cap U=U$ gilt. Wir könnten also aus der (angenommenen) Regularität von $X$ und $U$ mit der Durchschnittsstabilität der regulären Sprachen nur auf die Regularität von $U$ schließen, was keine neue Information wäre. So sieht man , dass bei dieser (!) Aufgabe die Betrachtung von $X\cap U$ wohl nicht weiterhilft. Bei anderen Aufgaben könnte hingegen die Betrachtung von einem Durchschnitt sehr wohl hilfreich sein.
Viele Grüße, Tobias ─ tobit 02.01.2022 um 23:05
vielen Dank für die Antwort, ich entschuldige die verspätete Rückmeldung und wünsche dir vorab ein frohes Neues!
Ich weiß das die Differenz zweier regulärer Sprachen ebenfalls eine reguläre Sprache ergibt, aber mir stellt sich die Frage nun woher man weiß welche Regel man einsetzen soll.
Weshalb hast Du beispielsweise X \ U ausgewählt und nicht X ( Durchschnitt ) U?
Gruß ─ user6d7173 02.01.2022 um 18:30