| Zeige Beiträge 1 bis 15 von 28 Treffern |
Seiten (2): [1] 2 nächste » |
 Thema: Problem mit Pumping-Lemma |
|
|
Hi Leute!
Ich hab hier ein paar Übungsaufgaben mit dem Pumping-Lemma. Ich hab damit aber schwere Probleme, dass Lemma zu verstehen. Wir machen hier übrigens die verschärfte Version davon.
![[latex]L =\{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L =\{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \})
Annahme: L ist regulär.
Sei ![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0) die Konstante des PL, dann gilt: ![[latex] n_0 \geq 1 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? n_0 \geq 1 ) und ![[latex]n_o \in \mathbb N [/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_o \in \mathbb N )
![[latex]z = 0^{2n_0} 1^{n_0} 0^{n_0} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?z = 0^{2n_0} 1^{n_0} 0^{n_0} ) mit ![[latex]|z| \geq n_0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php?|z| \geq n_0 ) und ![[latex] z \in \mathbb N [/latex]](http://www.matheboard.de/latex2png/latex2png.php? z \in \mathbb N )
Sei z=uvw eine Zerlegung von z mit: ![[latex]|uv| \leq n_0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php?|uv| \leq n_0 ) und ![[latex]|v| \geq 1 [/latex]](http://www.matheboard.de/latex2png/latex2png.php?|v| \geq 1 )
![[latex]z = uvw = 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow u = 0^{2n_0}, v = 1^{n_0} u = 0^{n_0} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?z = uvw = 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow u = 0^{2n_0}, v = 1^{n_0} u = 0^{n_0} )
Mein Problem ist nun, dass ich immer nicht weiß wie ich hier eine korrekte Zerlegung angebe. Diese hier oben sollte auch falsch sein, denke ich.
Könnt ihr mir helfen?
|
|
| Thema: Ist das hier Konkatenation eine von zwei Sprachen? |
|
|
Ich hab mir dann zur Konkatenation nochmals Gedanken gemacht und dabei auf den Automaten hier gekommen.
| Zitat: |
Original von Karlito
Überlege auch welche Konsequenz sich dann für den Finalzustand der ersten Sprache ergibt...
|
Ich verstehe jetzt in der Tat nicht so genau, was das jetzt mit den Finalzuständen auf sich hat. Kannst du vielleicht näher drauf eingehen?
|
|
| Thema: Aufgabe zu Abschlusseigenschaften |
|
|
Aufgabe:
Die Operation
![[latex]min: \mathbb P\left(\Sigma^{\star}\right) \to \mathbb P\left(\Sigma^{\star}\right)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?min: \mathbb P\left(\Sigma^{\star}\right) \to \mathbb P\left(\Sigma^{\star}\right))
sei definiert durch
![[latex]min(L)=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1: u \notin L \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?min(L)=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1: u \notin L \})
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.
Ich komm mit der Aufgabe nicht zurecht. Könnt ihr mir etwas weiterhelfen? Ich hab übrigens den Hopcroft als Lehrbuch. In diesem steht, dass gilt: Wenn L eine reguläre Sprache über dem Alphabt ![[latex]\Sigma[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Sigma) ist, dann ist ![[latex]\overline{L} = \Sigma^{\star} - L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\overline{L} = \Sigma^{\star} - L) auch eine reguläre Sprache.
Kann mir das da weiterhelfen? Gegeben ist ja nur die Sprache min(L). Wie ist dann eigentlich die Sprachdefinition für L alleine? Lautet die so: ![[latex]L=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1\}) ? Also eigentlich genauso wie min(L), nur, dass ![[latex]u \notin L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?u \notin L) fehlt; also, dass das echte Präfix mit enthalten ist.
Stimmt das alles soweit?
|
|
| Thema: Welche Sprache wird erkannt? |
|
|
Die Sache mit dem regulären Ausdruck hab ich mir auch schon gedacht. Da wir in der Vorlesung aber noch keine regulären Ausdrücke gemacht haben, kann es das als Lösung wohl eher nicht sein.
Die Mengeschreibweise wahrscheinlich schon eher. Aber wie kommt man dann von der Mengenschreibweise auf so eine Art mathematische Definition?
|
|
| Thema: Welche Sprache wird erkannt? |
|
|
Aufgabe: Welche Sprache erkennt M? -> Bild zum Automaten seht ihr unten!
Hi Leute!
Wie die Aufgabe ja bedeutet, soll ich die Sprache angeben, die den Automaten wie im Bild beschreibt. Ich hab mir dazu natürlich auch schon Gedanken gemacht und dabei auf das hier gekommen:
![[latex]L=\{ u1?? | u\in \Sigma^{\star} \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L=\{ u1?? | u\in \Sigma^{\star} \} ) mit ![[latex]\Sigma=\{0,1\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Sigma=\{0,1\})
Das u in meiner Sprache soll übrigens für ein Teilwort stehen und das wiederum für die Eigeschleife am ersten Zustand q. Dann MUSS eine 1 kommenn und dann gehts weiter zu den Fragezeichen; hier beginnen dann meine Probleme.
Wenn man den Automaten anschaut, kann man erkennen, dass nach Zustand 2 noch die Zustände 1 und 0 kommen, die jeweils mit einer 0 ODER einer 1 zu erreichen sind, also quasi jeweils ein Element aus .
Mein Problem ist nun, dass ich nicht weiß wie ich das in der formaler Mathematik ausdrücken soll...
Ich hoffe ihr könnt mir weiterhelfen!
|
|
| Thema: Ist das hier Konkatenation eine von zwei Sprachen? |
|
|
Danke, Karlito!
Das mit den verlinkten Bildern werd ich mir für die Zukunft merken!
Hm, dass die zwei Automaten falsch sind, hab ich jetzt nicht gedacht. Ich werd's nochmal neu versuchen.
| Zitat: |
| Der Automat M2 leistet das nicht. Z. B. ist das Wort 000 enthalten und die 1 allein wird nicht erkannt. |
Nehmen wir mal an es kommt der dezimale Zahlwert 1 des Wortes w. Zahlwert(w) repräsentiert dies ja, dann muss ich 1 % 3 = 1 rechnen. Dies ist aber nicht gleich 0 als darf der Automate nicht akzeptiere, was er auch nicht tut. Wenn nur eine einzige 1 kommt, bleibt der Automat beim nicht akzeptierenden Zustand P1 stehen!
| Zitat: |
| Beim zweiten nehme ich an, dass es keine führenden 0 geben darf oder die 0 steht allein. |
Hm, das finde ich bei dieser Aufgabe übrigens auch sehr schlecht formuliert. Woher soll ich wissen, ob führende Nullen nicht erlaubt sind? Wie man diesen Automaten allerdings realisieren soll, damit er führende Nullen nicht akzeptiert, weiß ich nicht. Aber: Wenn eine dezimale Null kommt, dann kommt es ja immer drauf an wie viel Bits zur Darstellung dieser dezimalen Zahl verwendet werden. Somit MUSS dieser Automate eigentlich führende Nullen akzeptieren, oder bin ich da jetzt komplett falsch gewickelt? Ich verstehe das so (ich verwende jetzt einfach für Demo-Zwecke eine 8-Bit-Zahl): ![[latex]0_{10} = 00000000_2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?0_{10} = 00000000_2) oder ![[latex]3_{10} = 00000011_2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?3_{10} = 00000011_2)
![[latex]L_1 = \{ w \in \Sigma^{\star}_{\text{Bool}} | w \text{ beginnt mit 00} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_1 = \{ w \in \Sigma^{\star}_{\text{Bool}} | w \text{ beginnt mit 00} \})
![[latex]L_2 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{Zahlwert(w) mod 3} = 0\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_2 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{Zahlwert(w) mod 3} = 0\})
Da es ja in der Aufgabenstellung heißt man darf auch epsilon-NEAs bauen, ist mein Vorschlag für die Konkatenation der beiden Automaten folgender:
EDIT: Wie kann man in diesem Forum, Bilder so schön unter Textblöcken anordnen, wie du es in deinem ersten Beitrag hier gemacht hast? Ich hab das leider nicht herausgefunden :-(
|
|
| Thema: Ist das hier Konkatenation eine von zwei Sprachen? |
|
|
Aufgabe:
Gegeben seien zwei endliche Automate M1 und M2. Geben Sie eine Konstruktionsvorschrift an, um daraus einen Automaten M3 mit ![[latex]L(M3) = L(M1) \cdot L(M2)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(M3) = L(M1) \cdot L(M2)) zu gewinnen.
Demonstrieren Sie Ihre Idee an der Sprache:
![[latex]L = \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{w beginnt mit 00}\} \cdot \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{Zahlwert(w) mod 3} = 0 \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L = \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{w beginnt mit 00}\} \cdot \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{Zahlwert(w) mod 3} = 0 \})
Hinweis: da hier nur allgemein von einem Automaten gesprochen wird, dürfen Sie nach Ihrer Wahl einen DEA, einen NEA oder einen ![[latex]\epsilon-NEA[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\epsilon-NEA) konstruieren.
Hi Leute!
Zur obigen Aufgabe hab ich mir natürlich schon Gedanken gemacht. Ich hab für die Sprache M1 bzw. M2 schon Automaten entworfen. Diese sieht man in diesem Link: Bild.
So, nun steht zwischen den beiden Sprachen in der Aufgabenstellung ein Malpunkt. Laut meinen Folien ist das die Konkatenation von zwei Sprachen bzw. Automaten. Aber wie geht das? ODER: Ist mit diesem Malpunkt der Produktautomat gemeint?
|
|
| Thema: Höhe eines Heaps |
|
|
Vollständige Teilaufgabe: Zeigen Sie die Aussage: Ein Heap mit n-Elementen hat die Höhe ![[latex] \lfloor log(n) \rfloor [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lfloor log(n) \rfloor ) .
Ich weiß, wenn ich einen Heap zeichne, dann entspricht die Höhe des Heaps in der Tat .
Ich hab unten ein Bild von meinem Heap.
Wie man sehen kann hat dieser Heap 7 Elemente, also n=7. Wenn ich nun die Höhe des Heaps berechnen will, gilt: ![[latex] h=\lfloor log_2(n) \rfloor = \lfloor log_2(7) \rfloor = 2 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? h=\lfloor log_2(n) \rfloor = \lfloor log_2(7) \rfloor = 2 )
Meine Frage: Wie aber zeigt man nun diese Aussage? Oder bin ich schon fertig?
|
|
| Thema: Reguläre Sprache und das Komplement |
|
|
Aufgabe
Gegeben sei das Alphabet ![[latex] \Sigma = \{0,1\} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \Sigma = \{0,1\} ) und die Sprache ![[latex]L_1 = \{ 0,00,000 \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_1 = \{ 0,00,000 \} )
Geben sie ![[latex] L_1^c [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L_1^c ) an.
In meinen Folien und Büchern und Internet hab ich leider nirgends eine gute Erklärung gefunden. Sprich ich weiß nicht was damit gemeint ist und auch nicht, wie die Lösung dazu aussieht. Könnt ihr mir weiterhelfen? Das ^c soll ja wohl Komplement bedeuten; also würde die Sprache L_1^c alle Wörter enthalten, die nicht in der Sprache L enthalten sind. Komplement eben. Wie aber sieht das dann hier konkret aus? Wie schreibt man das am besten hin?
So vielleicht: ![[latex] L_1^c = \{ 1,11,111 \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? L_1^c = \{ 1,11,111 \})
|
|
| Thema: Automatentheorie: DEA erstellen |
|
|
Hey Leute!
Frage:
Sei die Sprache L gegeben durch:
L = w \in \Sigma^{\star}_{\text{Bool}} | w \text{endet auf 01}}
Geben sie einen DEA an.
Wie gehe ich an sowas ran?
Ich soll jetzt hier quasi einen "deterministischen endlichen Automaten" aufzeichnen. Könnt ihr mir helfen wie man das macht? Grundkenntnisse hab ich natürlich. Er braucht akzeptierende Zustände, einen Anfangszustand und es geht immer nur mit einer 0 oder 1 weiter.
Könnt ihr mir helfen?
|
|
| Thema: Aufgabe zur Vorrangschreibweise? |
|
|
Hi Leute!
Ich hab folgende 3 Aufgaben die ich in die Vorrangschreibweise umschreiben soll. Ich hab schon Lösungen aber ich würde jetzt gern wissen ob das soweit richtig ist.
1. a+b-(x<=c|d)*t = -(+(a,b),*t(|d,(x(<=c))))
2. (c*d+a)*e = *(e,+(a,(*(c,d))))
3. a+b+c+d*e*f*g&x!=v = *(e,f,g,(!=(v,(&(x,(a,b,c,d)))))
Das "=" ist als mathematisches Istgleich zu verstehen, da ja quasi der Complier beide Schreibweisen als gleichwertig erkennen sollte...
Könnt ihr mir sagen ob ich korrekt gearbeitet habe?
|
|
| Thema: Bubblesort -> PAP |
|
|
Ich hab mir nochmal Gedanken gemacht und dabei gesehen, dass ich ja doch ein paar Fehler drin hatte. Unten mein neuer Ablaufplan. Ich weiß jetzt nur leider nicht wie ich dem Programm dann beibring wann es aufhören soll... Irgendwie check ich das grad nicht... Könnt ihr mir diesbezüglich helfen?
|
|
| Thema: Bubblesort -> PAP |
|
|
Hi Leute!
Ich soll zum Bubblesort-Algorithmus ein PAP schreiben. Mein bisheriges Ergebnis seht ihr unten im Bild. Meine Frage: Wenn ich die Zahl1[i]>Zahl2[i+1] verglichen habe und diese "Entscheidung" zu trifft, dann gehe ich in dem "Wahrzweig" weiter. Hier setze ich nun G=K; ich ersetze quasi die Zahl in G mit der Zahl in K. Was muss ich aber hier nun weiter tun? Irgendwie häng ich da grad ein bisschen... Könnt ihr mir weiterhelfen?
Den Ablauf des Bubblesorts hab ich soweit eigentlich verstanden: Vergleiche die Zahl ganz links mit der darauffolgenden rechten und vertausche die beiden Zahl falls die rechte davon kleiner als die linke ist...
Anfang 1. Durchlauf:
3 7 2 5 8 | vergleiche 3 mit 7
3 7 2 5 8 | vergleiche 7 mit 2; 2<7 es folgt: Vertauschung
3 2 7 5 8 | vergleiche 7 mit 5; 5<7 es folgt: Vertauschung
3 2 5 7 8 | vergleiche 7 mit 8; 7<8 es folgt: keine Vertauschung
Ende 1. Durchlauf
Anfang 2. Durchlauf:
3 2 5 7 8 | vergleiche 3 mit 2; 2<3 es folgt: Vertauschung
2 3 5 7 8 | vergleiche 3 mit 5; 3<5 es folgt: keine Vertauschung
2 3 5 7 8 | vergleiche 5 mit 7; 5<7 es folgt: keine Vertauschung
2 3 5 7 8 | vergleiche 7 mit 8; 7<8 es folgt: keine Vertauschung
Ende 2. Durchlauf es folgt: fertig Sortiert...
Danke!
|
|
|
| Zeige Beiträge 1 bis 15 von 28 Treffern |
Seiten (2): [1] 2 nächste » |
|
|
