 Aufgabe zu Sprachen |
David1979
Mitglied
Dabei seit: 26.09.2006
Beiträge: 27
 |
|
Hallo zusammen,
ich sitze gerade vor folgender Aufgabe und bin mir bei einer Sache nicht so sicher:
![[latex]L_{0} & = & \{ \epsilon \} \\ L_{k+1} & = & L_{k} \cup \{ uw:uw \in L_{k} \} \cup \{ (u):u \in L_{k} \} \\ L_{()} & = & \bigcup_{k} L_{k} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{0} & = & \{ \epsilon \} \\ L_{k+1} & = & L_{k} \cup \{ uw:uw \in L_{k} \} \cup \{ (u):u \in L_{k} \} \\ L_{()} & = & \bigcup_{k} L_{k} )
Die Sprache ![[latex]L_{3}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{3}) soll angegeben werden.
Heißt das ![[latex]\{ (u):u \in L_{k} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\{ (u):u \in L_{k} \}) , dass das andere ![[latex]u[/latex]](http://www.matheboard.de/latex2png/latex2png.php?u) ersetzt werden muss, so dass
![[latex]L_{0} & = & \{ \epsilon \} \\L_{1} & = & \{ (u)w, \epsilon \} \\L_{2} & = & \{ ((u))w ,(u)w, \epsilon \} \\L_{3} & = & \{ (((u)))w, ((u))w, (u)w, \epsilon \} \\L_{()} & = & \bigcup_{3} L_{3} = \{ (((u)))w, ((u))w, (u)w, \epsilon \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{0} & = & \{ \epsilon \} \\L_{1} & = & \{ (u)w, \epsilon \} \\L_{2} & = & \{ ((u))w ,(u)w, \epsilon \} \\L_{3} & = & \{ (((u)))w, ((u))w, (u)w, \epsilon \} \\L_{()} & = & \bigcup_{3} L_{3} = \{ (((u)))w, ((u))w, (u)w, \epsilon \})
Ist das ok?
|
|
29.10.2006 13:35 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
![[latex] \{ uw:uw \in L_{k} \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \{ uw:uw \in L_{k} \} ) ergibt für mich keinen Sinn. Soll es vielleicht ![[latex] \{ uw:u,w \in L_{k} \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \{ uw:u,w \in L_{k} \} ) heissen?
Wenn du nun einfach k=0 einsetzt dann kommst du zu der Formel: ![[latex]L_{1} = L_{0} \cup \{uw : u,w \in L_{0}\} \cup \{(u) : u \in L_{0} \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{1} = L_{0} \cup \{uw : u,w \in L_{0}\} \cup \{(u) : u \in L_{0} \} )
Da musst du dann alle möglichen u und w jeweils ein Element aus ![[latex] L_{0} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L_{0} ) einsetzen. In diesem Fall nur ![[latex] \epsilon [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \epsilon ) .
![[latex] L_{1} = \epsilon \cup \{ \epsilon \epsilon \} \cup \{ ( \epsilon ) \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L_{1} = \epsilon \cup \{ \epsilon \epsilon \} \cup \{ ( \epsilon ) \} )
Und da Epsilon für die leere Zeichenkette steht ist es dasselbe wie:
![[latex]L_{1} = \{ \epsilon, () \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{1} = \{ \epsilon, () \} )
u und w sind hier nur Variablen und kommen in den Wörtern der Sprache nicht vor.
Gruss,
ED209
|
|
|
29.10.2006 22:40 |
|
|
David1979
Mitglied
Dabei seit: 26.09.2006
Beiträge: 27
|
|
Das kann natürlich sein, dass es ![[latex]\{ uw:v,w \in L_{k} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\{ uw:v,w \in L_{k} \}) heißt. Habs aber hier richtig gepostet.
So wie du das beschrieben hast macht es aber wahrscheinlich wirklich mehr Sinn. Ich denke den Rest schaffe ich dann selber und danke übrigens für deinen Tip.
Gruß David
|
|
|
30.10.2006 11:26 |
|
|
kurellajunior 
Support
Dabei seit: 07.09.2006
Beiträge: 42
Herkunft: Von hier
|
|
Die Sprache scheint alle syntaktisch richtigen ANordnungen von einfachen Klammern zu beschreiben mit beliebiger Anordnung und Verschachtelung ohne Klammern zu verkreuzen.
Schönes Ding. Aber das komma im zweiten Ausdruck muss sein, da das sonst kein Sinn machen würde.
Poste dochmal deine Lösung, dann lässt sich am besten sehen, obs stimmt 
Jan
|
|
|
30.10.2006 17:56 |
|
|
David1979
Mitglied
Dabei seit: 26.09.2006
Beiträge: 27
|
|
![[latex]L_{0} & = & \{ \epsilon \} \\L_{1} & = & L_{0} \cup \{uw:u,w \in L_{0} \} \cup \{(u):u \in L_{0} \} \\L_{1} & = & \{ \epsilon \} \cup \{ \epsilon \epsilon \} \cup \{ (\epsilon) \} \\ L_{1} & = & \{ \epsilon, () \} \\ L_{2} & = & L_{1} \cup \{uw:u,w \in L_{1} \} \cup \{(u):u \in L_{1} \} \\ L_{2} & = & [\left \{ \epsilon \} \cup \{() \} \right] \cup [\left \{ ()() \} \cup \{ \epsilon () \} \cup \{ () \epsilon \} \right] \cup [\left \{ (\epsilon) \} \cup \{ (()) \} \right] \\ L_{2} & = & \{ \epsilon, (), ()(), (()) \} \\ L_{3} & = & L_{2} \cup \{uw:u,w \in L_{2} \} \cup \{(u):u \in L_{2} \} \\ L_{3} & = & \{ \epsilon ,(),()(),(()) \} \cup \{ ()()(), ()(()), (())()\} \cup \{(()()),((())) \} \\ L_{3} & = & \{ \epsilon ,(),()(),(()), ()()(), ()(()), (())(),(()()),((())) \} \\ L_{()} & = & \bigcup_{3} L_{3} = \{ \epsilon ,(),()(),(()), ()()(), ()(()), (())(),(()()),((())) \} \\ [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{0} & = & \{ \epsilon \} \\L_{1} & = & L_{0} \cup \{uw:u,w \in L_{0} \} \cup \{(u):u \in L_{0} \} \\L_{1} & = & \{ \epsilon \} \cup \{ \epsilon \epsilon \} \cup \{ (\epsilon) \} \\ L_{1} & = & \{ \epsilon, () \} \\ L_{2} & = & L_{1} \cup \{uw:u,w \in L_{1} \} \cup \{(u):u \in L_{1} \} \\ L_{2} & = & [\left \{ \epsilon \} \cup \{() \} \right] \cup [\left \{ ()() \} \cup \{ \epsilon () \} \cup \{ () \epsilon \} \right] \cup [\left \{ (\epsilon) \} \cup \{ (()) \} \right] \\ L_{2} & = & \{ \epsilon, (), ()(), (()) \} \\ L_{3} & = & L_{2} \cup \{uw:u,w \in L_{2} \} \cup \{(u):u \in L_{2} \} \\ L_{3} & = & \{ \epsilon ,(),()(),(()) \} \cup \{ ()()(), ()(()), (())()\} \cup \{(()()),((())) \} \\ L_{3} & = & \{ \epsilon ,(),()(),(()), ()()(), ()(()), (())(),(()()),((())) \} \\ L_{()} & = & \bigcup_{3} L_{3} = \{ \epsilon ,(),()(),(()), ()()(), ()(()), (())(),(()()),((())) \} \\ )
Ab habe ich nur alle neuen Klammerausdrücke hingeschrieben. Das wird sonst so unübersichtlich. War zunächst auch nicht so einfach wieder reinzukommen. Das mit den Sprachen ist schon etwas her, aber das müsste es eigentlich sein.
Gruß David
|
|
|
01.11.2006 12:37 |
|
|
kurellajunior
Support
Dabei seit: 07.09.2006
Beiträge: 42
Herkunft: Von hier
|
|
Guck mal. Bei der Bedingung ![[latex]\{uw:u,w\in L_{2}\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\{uw:u,w\in L_{2}\}) hast Du vier Sachen vergessen
Daher immer alles und Systematisch
![[latex]L_{0}&=&\{\epsilon \}\\ L_{1}&=&\{\epsilon,()\}\\ L_{2}&=&\{\epsilon,(),()(),(())\}\\ L_{3}&=&L_{2}\cup\{uw:u,w\in L_{2}\}\cup\{(u):u\in L_{2}\}\\ L_{3}&=&\{\epsilon,(),()(),(())\}\cup \Big\{\{()(),()()(),()(())\}\cup \{()()(),()()()(),()()(())\}\cup \{(())(),(())()(),(())(())\}\Big\}\cup \{(()()),((()))\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{0}&=&\{\epsilon \}\\ L_{1}&=&\{\epsilon,()\}\\ L_{2}&=&\{\epsilon,(),()(),(())\}\\ L_{3}&=&L_{2}\cup\{uw:u,w\in L_{2}\}\cup\{(u):u\in L_{2}\}\\ L_{3}&=&\{\epsilon,(),()(),(())\}\cup \Big\{\{()(),()()(),()(())\}\cup \{()()(),()()()(),()()(())\}\cup \{(())(),(())()(),(())(())\}\Big\}\cup \{(()()),((()))\})
|
|
|
02.11.2006 10:45 |
|
|
kurellajunior
Support
Dabei seit: 07.09.2006
Beiträge: 42
Herkunft: Von hier
|
|
| Zitat: |
Original von David1979
EDIT: Aber zumindest hab ich das Prinzip halbwegs verstanden
|
Stimmimt.
Viel Spaß noch. Und bei diesem Thema gbt es schonmal zwie kompetente Ansprechpartner hier. *gg* also her mit den Fragen.
Tschö
|
|
|
02.11.2006 12:55 |
|
|
|
danke dir