Informatiker Board | Druckvorschau: Aufgabe zu Sprachen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Aufgabe zu Sprachen (http://www.informatikerboard.de/board/thread.php?threadid=64)

Geschrieben von David1979 am 29.10.2006 um 13:35:

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?

Geschrieben von ed209 am 29.10.2006 um 22:40:

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

Geschrieben von David1979 am 30.10.2006 um 11:26:

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

Geschrieben von kurellajunior am 30.10.2006 um 17:56:

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

Geschrieben von David1979 am 01.11.2006 um 12:37:

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

Geschrieben von kurellajunior am 02.11.2006 um 10:45:

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

Geschrieben von David1979 am 02.11.2006 um 11:13:

Zunge raus!

ok, ich hab geschlafen. Zunge raus

danke dir

EDIT: Aber zumindest hab ich das Prinzip halbwegs verstanden smile

Geschrieben von kurellajunior am 02.11.2006 um 12:55:

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ö