Informatiker Board | Theoretische Informatik | Aufgabe zu Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » Aufgabe zu Sprachen » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 8 Beiträge

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ö

David1979

ok, ich hab geschlafen. Zunge raus

danke dir

EDIT: Aber zumindest hab ich das Prinzip halbwegs verstanden smile

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

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

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

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

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

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?