hat schon jemand einen lösumgsansatz für diese aufgabe?

Wenn du die Aufgabenstellung beschreiben würdest, könnten auch Leute antworten, die kein FGI hören. [22]

EDIT: Es gibt hier einige im Forum, die sich mit Theorie ganz gut auskennen und hier auch viel erklären. [23]

die aufgabe gibt es hier

http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe07/aufg1.pdf

ich weiss nicht in welcher form ich dies "zeigen" soll…

sollen wir dann erstmal ne grammatik definieren und zeigen, dass sie für alle fälle funktioniert?

Im Prinzip musst du nur die fünf angegebenen Fälle durchgehen und zeigen, dass jeder eine RA-Sprache ist.
ZB. sind ja {1} und {0} RA-Sprachen und folglich auch {10}, {11}, {00} und {01}. Diese Sprachen muss man dann nur noch für die einzelnen Fälle kombinieren.

was meinst du mit kombinieren?

Konkatenation, Vereinigungsmengen…
Halt das, was auch in der Aufgabe angegeben ist.

dann haben wir also endlos lange zeichenketten über sigma. ich betrachten dann die verschiedenen fälle. wie zb 11 und 00 kommen gar nicht vor. ist das dann nicht eine endlose kette von 01010101…..? i

ch steig da irgendwie noch nich ganz durch wie man jetzt zeigen soll das es eine RAsprache ist.

[latex]\{0\}[/latex] und [latex]\{1\}[/latex] sind RA-Sprachen, also auch [latex]\{0\} \circ \{1\} = \{01\}[/latex] uswusf.

[latex]\{0\}[/latex] und [latex]\{1\}[/latex] sind RA-Sprachen, also auch [latex]\{0\} \circ \{1\} = \{01\}[/latex] uswusf.

und das soll dann zeigen, dass es im ersten fall stimmt?

In der Aufgabe steht doch, dass wenn A eine RA-Sprache ist, auch A* eine RA-Sprache ist.
Bei {01} wären das sämtliche "Ketten" {01…}. Dann kann am Anfang noch eine 1 und am Ende noch eine 0 stehen.

Das schriebe man dann in etwa so: {1,epsilon}{01}*{0,epsilon}

In der Aufgabe steht doch, dass wenn A eine RA-Sprache ist, auch A* eine RA-Sprache ist.
Bei {01} wären das sämtliche "Ketten" {01…}. Dann kann am Anfang noch eine 1 und am Ende noch eine 0 stehen.

Das schriebe man dann in etwa so: {1,epsilon}{01}*{0,epsilon}

ich habe da nochmal ne frage zur schreibweise. wir haben ja das alphabet {0,1}

ist dein beispiel {1,epsilon}{01}{0,epsilon} dann jetzt eine zeichenkette über sigma?

und wir geben für alle möglichen fälle die zeichenketten an?

und wie schreiben wir das dann auf? wie nennen wir {1,epsilon}{01}{0,epsilon} ?

schreiben wir das auf als element von L_2?

Das Beispiel stellt eine Sprache (X) dar. X = {1,epsilon}{01}*{0,epsilon}
In geschweiften Klammern steht ja jeweils eine RA-Sprache. Und die konkatierst du dann halt miteinander, so dass (laut Definition) wieder eine neue RA-Sprache entsteht.
Das Sternchen bei {01} ist übrigens wichtig, weil ja auch mehrmals das Symbol "01" benutzt werden kann.

Das Beispiel stellt eine Sprache (X) dar. X = {1,epsilon}{01}*{0,epsilon}
In geschweiften Klammern steht ja jeweils eine RA-Sprache. Und die konkatierst du dann halt miteinander, so dass (laut Definition) wieder eine neue RA-Sprache entsteht.
Das Sternchen bei {01} ist übrigens wichtig, weil ja auch mehrmals das Symbol "01" benutzt werden kann.

ok, vielen dank. ich habe das sternchen mit der konkatenotion verwechselt.

und das hast du jetzt für alle der genannten fälle getan? wie machst du das dann bei fall 4 und 5 wenn die eine folge irgendwann vor der anderen kommt?

Probiere einfach ein wenig rum und schau noch mal ins Script. Dabei lernst du das ganze am besten.
Schreib dir auf, wie die Folge aussehen soll und dann konkatierst du die entsprechenden Sprachen.

gilt die sprache {1,1}* für alle geraden und ungeraden folgen von {1,1,1,……}?

ne das müsste sein {1}{1}* ?

oder reicht {1}* ?

wenn im zweiten fall nur die folge 11 vorkommt, heisst das, dass aber auch 01 vorkommen kann?

Ja, 01 kann vorkommen, sogar beliebig oft.

gut, dass ich das in der letzten stunde nochmal verbessert habe ;)