Abgeschlossenheit < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe:
Die Operation
$min: [mm] \mathbb P\left(\Sigma^{\star}\right) \to \mathbb P\left(\Sigma^{\star}\right)$
[/mm]
sei definiert durch
[mm] $min(L)=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1: u \notin L \}$
[/mm]
min beinhaltet also alle diejenigen Wörter aus L, deren echten Präfixe nicht in L liegen. Sei nun L eine reguläre Sprache, ist dann auch min(L) regulär?
Begründen Sie Ihre Antwort. |
Hi Leute!
Ich hab zu dieser Aufgabe einige Fragen:
Hier geht es ja um die Abschlusseigenschaften regulärer Sprachen. Soweit so gut. Welche Operationen, auf reguläre Sprachen angewandt, abgeschlossen sind, weiß ich.
Meine Lösung:
-> L ist regulär (durch Aufgabenstellung vorgegeben)
Nun konstruieren ich mir eine neue Sprache [mm] $L_{min} [/mm] = [mm] \{ z \in L | \forall x,y \in \Sigma^{\star} \text{ mit } z=xy, 1 \leq |x|, |y| \geq 1: y \notin L \}$. [/mm] Jetzt ist aber noch nicht gesagt, dass diese "neue Sprache" auch wirklich regulär ist. Um zu beweisen, dass eine Sprache regulär ist, habe ich gelernt, dass man einen Automaten bauen kann. Und genau da fangen jetzt meine Probleme an. Ich weiß nicht wie ich einen solchen Automaten für diese Sprach [mm] $L_{min}$ [/mm] konstruieren soll.
-> Nehmen wir nun mal an, dass ich einen Automaten für [mm] $L_{min}$ [/mm] konstruiert hätte <-
-> Die Differenz zweier regulärer Sprachen ist regulär. (Lehrsatz aus Hopcroft)
Somit kann ich doch dann schreiben: $min(L) = L - [mm] L_{min}$ [/mm] Ich weiß hier laut Aufgabe, dass L regulär ist und durch die Konstruktion des Automaten von [mm] $L_{min}$ [/mm] weiß ich auch, dass [mm] $L_{min}$ [/mm] regulär ist. Somit subtrahiere ich zwei reguläre Sprachen voneinander wodurch $min(L) auch wieder regulär ist. Durch die Eigenschaft von [mm] $L_{min}$ [/mm] ist sichergestellt, dass $min(L)$ genau diese Teilmenge enthält, die durch die Aufgabe gefordert ist.
Stimmt das soweit?
Edit:
Ich denke mittlerweile, dass die Aufgabe so auch gelöst bzw. überhaupt erst richtig gelöst ist:
-> L ist regulär (aus Aufgabe)
-> [mm] $L_{min} [/mm] = [mm] \{ z \in L | \forall x,y \in \Sigma^{\star} \text{ mit } z=xy, 1 \leq |x|, |y| \geq 1: y \notin L \}$ [/mm] davon aber nun das Komplement, da man einen Automaten konstruieren kann ist die Sprache regulär
min(L) ist regulär, da L und [mm] $L_{min}$ [/mm] regulär ist sowie die Mengendifferenz angewandt auf zwei reguläre Sprachen wieder eine reguläre Sprache ergibt:
$min(L) = L - [mm] \overline{L_{min}}$
[/mm]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Fr 01.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
