Abschlusseigenschaften regulärer Sprachen

Erste Frage Aufrufe: 61     Aktiv: 02.01.2022 um 23:05

0
Hey Leute,

leider habe ich einige Verständnisprobleme bei Folgender Übung: ( siehe Bild ).
Generell das ganze Thema "Pumping Lemma" macht mir etwas zu schaffen, jedoch ist mir die Vorgehensweise bewusst und die Aufgaben dazu konnte ich lösen, nur bei der Aufgabe anhand von Abschlusseigenschaften zu beweisen dass eine Sprache regulär oder nicht regulär ist verstehe ich leider nicht und konnte im Internet dazu nichts passendes finden.
Daher hoffe ich eventuell Hier auf eine passende Antwort zu treffen.

Die Aufgabe:




Danke im Voraus!
Diese Frage melden
gefragt

Student, Punkte: 10

 
Kommentar schreiben
1 Antwort
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
Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 200

 

Hallo Tobias,

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

Deswegen fragt er doch, was $X\setminus U$ mit $V$ zu tun hat. Mach dir das doch einmal klar. Dann beantwortet sich auch die Frage, warum man das gerade so auswählt und wo genau das dann zum Widerspruch führt.   ─   cauchy 02.01.2022 um 19:28

1
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

Kommentar schreiben