Aufgabe zu Sprachen

29.10.2006, 13:35

David1979

Aufgabe zu Sprachen

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]$
Die Sprache $[latex]L_{3}[/latex]$ soll angegeben werden.

Heißt das $[latex]\{ (u):u \in L_{k} \}[/latex]$ , dass das andere [latex]u[/latex]

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]$

Ist das ok?

29.10.2006, 22:40

Auf diesen Beitrag antworten »

ed209

RE: Aufgabe zu Sprachen

$[latex] \{ uw:uw \in L_{k} \} [/latex]$ ergibt für mich keinen Sinn. Soll es vielleicht $[latex] \{ uw:u,w \in L_{k} \} [/latex]$ 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]$

Da musst du dann alle möglichen u und w jeweils ein Element aus $[latex] L_{0} [/latex]$ einsetzen. In diesem Fall nur $[latex] \epsilon [/latex]$ .

$[latex] L_{1} = \epsilon \cup \{ \epsilon \epsilon \} \cup \{ ( \epsilon ) \} [/latex]$

Und da Epsilon für die leere Zeichenkette steht ist es dasselbe wie:

$[latex]L_{1} = \{ \epsilon, () \} [/latex]$

u und w sind hier nur Variablen und kommen in den Wörtern der Sprache nicht vor.

Gruss,
ED209

30.10.2006, 11:26

Auf diesen Beitrag antworten »

David1979

RE: Aufgabe zu Sprachen

Das kann natürlich sein, dass es $[latex]\{ uw:v,w \in L_{k} \}[/latex]$ 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, 17:56

Auf diesen Beitrag antworten »

kurellajunior

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 Augenzwinkern

Jan

01.11.2006, 12:37

Auf diesen Beitrag antworten »

David1979

$[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]$

Ab $[latex]L_{3}[/latex]$ 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

02.11.2006, 10:45

Auf diesen Beitrag antworten »

kurellajunior

Guck mal. Bei der Bedingung $[latex]\{uw:u,w\in L_{2}\}[/latex]$ hast Du vier Sachen vergessen Augenzwinkern

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]$

02.11.2006, 11:13

Auf diesen Beitrag antworten »

David1979

ok, ich hab geschlafen. Zunge raus

danke dir

EDIT: Aber zumindest hab ich das Prinzip halbwegs verstanden smile

02.11.2006, 12:55

Auf diesen Beitrag antworten »

kurellajunior

Zitat:

Original von David1979
EDIT: Aber zumindest hab ich das Prinzip halbwegs verstanden smile

Stimmimt.

Viel Spaß noch. Und bei diesem Thema gbt es schonmal zwie kompetente Ansprechpartner hier. *gg* also her mit den Fragen.

Tschö

Neue Frage »

Antworten »

Aufgabe zu Sprachen

Verwandte Themen