Mengenproblem < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:07 Do 19.01.2012 | | Autor: | bandchef |
| Aufgabe | Gegeben sind die zwei Mengen L1 = {A,B,C} und L2 = {D,E,F}.
Die Elemente C, D, E sind "akzeptierend".
Weiterhin ergeben sich diese neuen Teilmengen: T1 = {A,D}; T2 = {B,E}; T3 = {B,F}; T4 = {C,D}; T5 = {C,F} und T6 = {A,F}.
Markieren sie nun die Teilmenge, für die gilt: Tn = L2 - L1. |
Hi Leute!
Hier geht's dann wohl um Mengen. Besser gesagt eigentlich um die Mengendifferenz. Was ich mir bis jetzt schon mal angeeignet habe ist die Definition der Differenz:
Tn = L2 - L1 = L2 \ L1 = [mm] $\{x | x \in L2 \wedge x \notin L1 \}$
[/mm]
Das sollte doch soweit, angewendet auf meine Aufgabe stimmen, oder? Das Problem dabei ist, dass ich irgendwie doch noch nicht so wirklich weiß welche Tupel aus meinen Teilmengen ich nun markieren soll.
Ich hab dennoch mal versucht meine Gedanken in Wort zu fassen und bin auf das hier gekommen: Die akzeptierenden Elemente aus L1 dürfen nicht in Tn enthalten sein.
Stimmt das soweit? Könnt ihr mir helfen?
|
|
| |
|
Hiho,
erstmal ein paar klärende Fragen:
> Gegeben sind die zwei Mengen L1 = {A,B,C} und L2 =
> {D,E,F}.
Ok
> Die Elemente C, D, E sind "akzeptierend".
Was heißt das? Den Begriff habe ich in der Mathematik noch nie gehört und Google sagt auch nix dazu.
> Weiterhin ergeben sich diese neuen Teilmengen:
Woraus?
> Hier geht's dann wohl um Mengen. Besser gesagt eigentlich
> um die Mengendifferenz. Was ich mir bis jetzt schon mal
> angeeignet habe ist die Definition der Differenz:
>
> Tn = L2 - L1 = L2 \ L1 = [mm]\{x | x \in L2 \wedge x \notin L1 \}[/mm]
> Das sollte doch soweit, angewendet auf meine Aufgabe
> stimmen, oder?
Das macht keinen Sinn. Das ist zwar die Definition der Mengendifferenz in der Mathematik, würde in Bezug auf die Aufgabenstellung aber gar keinen Sinn machen!
Denn: [mm] $L2\setminus [/mm] L1 = [mm] \{D,E,F\}\setminus\{A,B,C\} [/mm] = [mm] \{D,E,F\} [/mm] = L2 [mm] \not= T_n \quad\forall [/mm] n$
Also: Mehr Informationen! Vorallem ausfindig machen, wie euer "Minus" definiert ist.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:42 Do 19.01.2012 | | Autor: | bandchef |
Akzeptierend heißt, dass der Automat in diesem Zustand stehen bleibt, eben "akzeptiert". Es handelt sich um Automatentheorie.
L1 und L2 sind Zustandsmengen zweier unterschiedlicher Automaten. Woraus nun diese Teilmengen entstehen ist jetzt schwierig zu erklären. Sagt dir "Produktautomat" was?
Jede dieser neuen Teilmengen sind quasi ein Zustand des neuen Produktautomaten. Laut unserer Vorlesung handelt es sich bei der Mengendifferenz um die mathematische Mengendifferenz wie man sie kennt!
Ich hoffe, dass ihr euch jetzt ein besseres Bild meines Problems machen könnt!
|
|
|
| |
|
Hiho,
> Akzeptierend heißt, dass der Automat in diesem Zustand
> stehen bleibt, eben "akzeptiert". Es handelt sich um
> Automatentheorie.
Hab ich vermutet.
> L1 und L2 sind Zustandsmengen zweier unterschiedlicher
> Automaten. Woraus nun diese Teilmengen entstehen ist jetzt
> schwierig zu erklären. Sagt dir "Produktautomat" was?
Jo, man bildet halt einfach das Kreuzprodukt.
D.h. der neue Automat hat einfach die Zustände
[mm] $L_1 \times L_2 [/mm] = [mm] \left\{(A,D),(A,E),(A,F),(B,D),(B,E),(B,F),(C,D),(C,E),(C,F)\right\}$
[/mm]
Was davon Endzustände sind, hängt davon ab ob du einen "oder"-Automaten hast oder einen "und"-Automaten.
Nun sind halt deine Teilmengen daraus gegeben, die (wie man sieht) Zustände des Produktautomaten sind.
> Laut unserer Vorlesung handelt es
> sich bei der Mengendifferenz um die mathematische
> Mengendifferenz wie man sie kennt!
Das glaub ich dir, hab aber im ersten Post auch schon gezeigt, dass das hier keinen Sinn macht, denn [mm] $L_2 [/mm] - [mm] L_1 [/mm] = [mm] L_2$ [/mm] !
> Ich hoffe, dass ihr euch jetzt ein besseres Bild meines
> Problems machen könnt!
Ja, nur das Problem mit der Differenz besteht noch immer.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:08 Do 19.01.2012 | | Autor: | bandchef |
Das Differenzen-Problem besteht also weiterhin. Was soll ich jetzt machen? Laut Aufgabe soll ich aber die akzeptierenden Zustände im neuen "Produktautomaten" laut dieser Vorschrift Tn = L2 - L1 angeben. Ist dann die Aufgabe falsch?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:14 Do 19.01.2012 | | Autor: | bandchef |
Ich glaube ich muss da einfach noch mehr dazu posten.
Man sollte aus gegeben Sprachen erstmal zwei DEA's konstruieren.
$L1 = [mm] \{w \in \Sigma^\star_\text{Bool} | \text{w endet auf 01}\}$
[/mm]
$L2 = [mm] \{w \in \Sigma^\star_\text{Bool} | \text{w enthält 00 nicht}\}$
[/mm]
Wenn man die zwei DEA's hat, soll man nun den Automaten L = L2 - L1 mit Produktautomatenkonstruktion erzeugen.
Hier haben wir nun in der Vorlesung gelernt, dass eben die Differenz die ganz normale Differenz ist. Die Differenz bezieht sich ja auch "nur" auf die akzeptierende(n) Zustände des "neuen" Automaten!
PS: Ich kann mir halt schwer vorstellen, dass die Aufgabe schwachsinn ist, da das eine Prüfungsaufgabe war...
|
|
|
| |
|
Hiho,
ahjo, so macht die Aufgabe ja nun mehr Sinn 
> Ich glaube ich muss da einfach noch mehr dazu posten.
Warum nicht gleich so 
> Man sollte aus gegeben Sprachen erstmal zwei DEA's
> konstruieren.
>
> [mm]L1 = \{w \in \Sigma^\star_\text{Bool} | \text{w endet auf 01}\}[/mm]
Ok, dass das nen Automat mit drei Zuständen ist, wo einer nen Endzustand ist, seh ich ein
> [mm]L2 = \{w \in \Sigma^\star_\text{Bool} | \text{w enthält 00 nicht}\}[/mm]
Auch hier: 3 Zustände, 2 Endzustände. Soweit klar.
> Wenn man die zwei DEA's hat, soll man nun den Automaten L =
> L2 - L1 mit Produktautomatenkonstruktion erzeugen.
Jo, und nun mach dir mal klar, was das für eine Menge ist:
$L = L2 - L1 = [mm] \{w \in \Sigma^\star_\text{Bool} | \text{w enthält 00 nicht}\} \setminus \{w \in \Sigma^\star_\text{Bool} | \text{w endet auf 01}\} [/mm] = [mm] \{w \in \Sigma^\star_\text{Bool} | \text{w enthält 00 nicht und endet nicht auf 01}\}$
[/mm]
Die Frage ist ja nun eigentlich, welche Zustände [mm] T_n [/mm] sind die akzeptierten Zustände für L, also für welche n gilt [mm] $T_n \in [/mm] L$ (und das war ja eigentlich deine Ursprungsfrage, das ist aber Informatikerschreibweise, darum die anfängliche Verwirrung ).
Mach dir dafür mal klar, dass der Produktautomat für die Differenz gerade die Zustände akzeptieren muss, die für [mm] L_2 [/mm] ein Endzustand sind, für [mm] L_1 [/mm] aber gerade nicht!
Welche sind das?
Als Übung kannst du ja auch gleich mal prüfen für welche Zustände [mm] $T_n \in L_1*L_2$ [/mm] bzw [mm] $T_n \in L_1+L_2$ [/mm] gilt.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:07 Fr 20.01.2012 | | Autor: | bandchef |
| Aufgabe | Entwerfen sie einen nichtdeterministischen Automaten aus den folgenden Sprachen:
La = [mm] \{ w \in \Sigma^\star_{\text{Bool}} | |w|_0 = 4 \wedge |w|_1 mod 2 = 0\}
[/mm]
Lb = [mm] \{ w \in \Sigma^\star_{\text{Bool}} | \text{w enthält 1010 als Teilwort}\} [/mm] |
Erstmal danke für tolle deine Hilfe! Ich hab jetzt die Differenz soweit verstanden
Ich hätt hier jetzt noch eine weitere Aufgabe. Vielleicht magst du mir nochmal helfen, bzw. meine bisherige Lösung mal durchschaun und sagen ob das stimmt? Den Aufgabentext findest du oben.
Hier ist ein link zu meiner Lösung: http://imageshack.us/photo/my-images/580/78685382.jpg/
[Ü07.3/3]
|
|
|
| |
|
Hiho,
Das gute vorweg: [mm] L_b [/mm] ist korrekt.
Zu [mm] $L_a$: [/mm] Ich vermute einfach mal, dass [mm] $|\omega|_0$ [/mm] die Anzahl an Nullen in [mm] \omega [/mm] ist.
Dann schau dir deinen Automaten mal nochmal an, dieser akzeptiert z.B. auch [mm] $\omega [/mm] = 1000 [mm] \not\in L_a$
[/mm]
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:04 Sa 21.01.2012 | | Autor: | bandchef |
Ich glaube ich hab hier schon irgendwie Probleme, die Sprache richtig zu interpretieren.
Das [mm] $\wedge$ [/mm] zwischen den beiden Eigenschaften am Schluss liest sich hier doch als "und zugleich", oder?
Das heißt, der Automat muss Wörter erkennen die genau zwei 1er "und zugleich" vier 0er drin haben, oder? Oder bedeutet die Sprache, dass der Automat beide Einschränkungen erkennen muss? Weil "gleichzeitig" (so wie man sich das vorstellt) geht das ja wohl nicht, oder?
Oder verstehe ich die Sprache schon nicht?
Dann noch ein paar grundsätzliche Fragen zu einem NEA. Dürfen von einem Zustand in einem NEA auch mehr Transitionen weggehen als 2? Darf in einem NEA auch nur eine Transition eines Zustands weggehen?
PS: Mein neuer Vorschlag sieht so aus: http://imageshack.us/photo/my-images/715/25253154.jpg/
PPS: Wobei ich grad sehe, dass er ja immer noch 1000 akzeptiert :-( Ich weiß da jetzt leider nicht so genau weiter...
|
|
|
| |
|
Hiho,
> Ich glaube ich hab hier schon irgendwie Probleme, die
> Sprache richtig zu interpretieren.
Das stelle ich auch gerade fest
> Das [mm]\wedge[/mm] zwischen den beiden Eigenschaften am Schluss
> liest sich hier doch als "und zugleich", oder?
Ja.
> Das heißt, der Automat muss Wörter erkennen die genau
> zwei 1er "und zugleich" vier 0er drin haben, oder?
Nein, du hast noch nicht ganz verstanden, was "mod" genau bedeutet.
Aber erstmal das Positive: Ja, es müssen GENAU 4 Nuller drin sein.
[mm] $|\omega|_1 \text{ mod } [/mm] 2 = 0$
bedeutet, dass die Anzahl an Einsen durch 2 teilbar sein muss (und das ist nicht nur 2, sondern auch 0,4,6,8,....)
> bedeutet die Sprache, dass der Automat beide
> Einschränkungen erkennen muss? Weil "gleichzeitig" (so wie
> man sich das vorstellt) geht das ja wohl nicht, oder?
Warum sollte es nicht gehen? 110000 oder 001100 erfüllen diese Bedingungen doch.
> Dann noch ein paar grundsätzliche Fragen zu einem NEA.
> Dürfen von einem Zustand in einem NEA auch mehr
> Transitionen weggehen als 2?
Ja, der Automat kann sich dann "aussuchen", welchen Weg er beschreitet.
Ein Wort wird dann akzeptiert, wenn es einen möglichen Weg in einen Endzustand gibt.
> Darf in einem NEA auch nur eine Transition eines Zustands weggehen?
Nein, der Automat muss natürlich immer wissen, wie er mit einer Eingabe umzugehen hat.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:17 Sa 21.01.2012 | | Autor: | bandchef |
So, dann hier nochmal ein Versuch den Automaten zu zeichnen. Vielleicht kannst du ja mal überprüfen, oder so. Link: http://imageshack.us/photo/my-images/46/86472200.jpg/
|
|
|
| |
|
Huhu,
leider nein.
Das sieht man schon daran, dass das Wort [mm] $\omega [/mm] = 0$ akzeptiert wird.
Als Tip: Du wirst nicht mit weniger als 4 Zuständen auskommen, denn du musst deine Anzahl an Nullen ja mitzählen.
Sobald du 4 Nullen hast, darfst du in den Endzustand wechseln, aber nur, wenn du eine gerade Anzahl an Einsen hast.
Das tolle an einem Automaten ist ja, dass du nicht den "optimalen" Automaten finden musst.
Also schreib doch alle deine Fälle mal auf in der Form:
Keine Null, Gerade Anzahl an Einsen
Keine Null, Ungerade Anzahl an Einsen
Eine Null, Gerade Anzahl an Einsen
...
Und schon hast du alle deine Zustände
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:08 So 22.01.2012 | | Autor: | bandchef |
Also, dann geh ich mal den Automaten nach deiner Art und Weise an. Ich hab jetzt mal alle Möglichkeiten aufgeschrieben:
- keine 0, gerade 1
- keine 0, ungerade 1
- eine 0, gerade 1
- eine 0, ungerade 1
- zwei 0, gerade 1
- zwei 0, ungerade 1
- drei 0, gerade 1
- drei 0, ungerade 1
- vier 0, gerade 1
- vier 0, ungerade 1
Akzeptiert werden sollte doch eigentlich nur der vorletzte Zustand, also "vier 0, gerade 1". Das ist doch das was die Sprache fordert, oder?
Ich hab's dann gleich nochmal versucht umzusetzen: http://imageshack.us/photo/my-images/692/31552881.jpg/
Vielleicht stimmt der Automat ja jetzt... Sicher bin ich mir immer noch nicht
|
|
|
| |
|
Hiho,
> Also, dann geh ich mal den Automaten nach deiner Art und
> Weise an. Ich hab jetzt mal alle Möglichkeiten
> aufgeschrieben:
>
> - keine 0, gerade 1
> - keine 0, ungerade 1
> - eine 0, gerade 1
> - eine 0, ungerade 1
> - zwei 0, gerade 1
> - zwei 0, ungerade 1
> - drei 0, gerade 1
> - drei 0, ungerade 1
> - vier 0, gerade 1
> - vier 0, ungerade 1
>
> Akzeptiert werden sollte doch eigentlich nur der vorletzte
> Zustand, also "vier 0, gerade 1". Das ist doch das was die
> Sprache fordert, oder?
Genau
> Ich hab's dann gleich nochmal versucht umzusetzen:
> http://imageshack.us/photo/my-images/692/31552881.jpg/
Wobei natürlich die Frage aufkommt: Warum hat dein Automat nur 5 Zustände, wenn du doch festgestellt hast, dass du MINDESTENS 8 Fälle brauchst? Welche Fälle von oben kannst du denn deiner Meinung nach zusammenfassen?
Ausserdem braucht es mindestens einen absorbierenden Zustand, d.h. einen Zustand, wo man NIE wieder rauskommt.
Ab der 5. Null wird das Wort nämlich keinesfalls akzeptiert, egal was dort noch kommt.
Dein Automat akzeptiert jedes Wort, was eine gerade Anzahl an Zeichen hat (wechsel beliebig zwischen [mm] q_0 [/mm] und [mm] q_5 [/mm] hin und her).
MFG,
Gono.
> Vielleicht stimmt der Automat ja jetzt... Sicher bin ich
> mir immer noch nicht
|
|
|
| |
|
| Aufgabe | | Hier ist die Aufgabe: http://imageshack.us/photo/my-images/18/85643652.jpg/ |
Teilaufgabe a) hab ich soweit: [mm] $L=\{w \in \Sigma^\star_{\text{Bool }} | w = u01v10 \text{ mit } u,v \in \Sigma^\star_{\text{Bool}}\}
[/mm]
Bei b) hab ich Probleme:
Ich hab mir hier nun erst einen DEA erstellt. Vorgehensweise: Aus dem NEA (der war gegeben) einen DEA durch Potenzmengenkonstruktion erstellen. Der sieht dann so aus: http://imageshack.us/photo/my-images/542/83629798.jpg/
Nun hab ich aber ein Problem mit dem [mm] $L^C$. [/mm] Laut meiner Formelsammlung ist [mm] $L^C [/mm] = A [mm] \textbackslash [/mm] B = A-B$. Um diese Mengendifferenz haben wir uns ja jüngst erst gekümmert. Jetzt hab ich aber das Problem, dass ich ja keine zwei Sprachen hab, sondern nur die eine einzige oben angegebene Sprache...
Wie soll das nun gehen?
PS: Die Konstruktion des Automaten mit den 8 Zuständen hab ich mal vorerst auf Eis gelegt. Es erscheint mir jetzt der eine Automat nicht so wichtig...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mi 25.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
