alphabete, wörter, sprachen

15.04.2013, 09:48

noobee

alphabete, wörter, sprachen

zwei aufgaben, bei denen ich icht wei wie ich anfangen soll bzw was zu machen ist unglücklich

gesucht sind wörter, welche in/nicht in der menge £={a,b} sind.

1: {w∈£* | ∃u,v∈£*: uvw=vwu}
2: {w∈£* | ww=www}

15.04.2013, 09:54

Auf diesen Beitrag antworten »

noobee

hier nochmal richtig

zwei aufgaben, bei denen ich icht wei wie ich anfangen soll bzw was zu machen ist unglücklich

gesucht sind wörter, welche in/nicht in der menge sigma={a,b} sind.

1: {w ist element aus sigma* | exist. u,v aus sigma*: uvw=vwu}
2: {w ist element aus sigma* | ww=www}

15.04.2013, 10:19

Auf diesen Beitrag antworten »

Airblader

Gemeint ist wohl, dass das Sprachen über dem Alphabet {a,b} sein sollen. Falls du wirklich gar keine Ahnung hast, was zu tun ist: Ist dir überhaupt klar, was eine formale Sprache ist? Wenn nein, dann erst nochmal nachlesen.

Für die 1. nehmen wir uns mal das einfachste Element aus dem Alphabet, das wir uns denken können: w = a. Liegt a in der ersten Sprache?

15.04.2013, 10:46

Auf diesen Beitrag antworten »

noobee

naja also ich denke einfach mal laut verwirrt

sigma={a,b} sagt, dass mein alphabet nur die buchstaben a und b hat.
sigma* sind alle wörter, die man mit a,b bilden kann.

zu 1.: w ist elem aus sigma* bedeutet doch, dass es ein wort w gibt, welches aus den buchstaben a,b besteht. also bspw. das wort "aabbabab".
was bedeutet aber, dass nun noch ein u,v aus sigma* exis., so dass uvw=vwu gilt ?

zu 2.: w ist elem aus sigma* und es gilt ww=www. also das wort w ist bspw. "abbab". wenn ich das nun in ww und www einsetze kommt ja nicht das gleiche raus, denn

abbababbab != abbababbababbab
das ist ww != das ist www

15.04.2013, 11:37

Auf diesen Beitrag antworten »

Airblader

Ah, das Problem liegt also woanders.

$[latex]\{w \in \Sigma^* ~|~ \exists_{u, v \in \Sigma^*} : uvw = vwu \}[/latex]$

beschreibt die Sprache aller Wörter $[latex]w \in \Sigma^*[/latex]$ mit der Eigenschaft, dass es $[latex]u, v \in \Sigma^*[/latex]$ gibt, so dass [latex]uvw = vwu[/latex]

gilt. Soll heißen: Der linke Teil sagt nur wie wir Wörter dieser Sprache nennen wollen (w) und wo sie herkommen (eben aus dem Alphabet) und der rechte Teil beschreibt dann, welche Bedingungen für w gelten müssen, so dass es auch wirklich in der Sprache liegt.

Hilft das schon weiter?

15.04.2013, 15:21

Auf diesen Beitrag antworten »

noobee

Zitat:

Hilft das schon weiter?

mhh, will ja nicht unhöflich sein, aber "nein", hilft nicht weiter Augenzwinkern

also ich kann das schon "übersetzen" was da steht, also es existiert ein u,v aus ...

aber ich weiß nicht, was mir das sagen soll. es muss ja gelten uvw=vwu.
ich weiß aber nur, dass das w aus sigma* (also {a,b}) sein kann.

setze ich jetzt in das w dann a oder b ein ?? also uvw wäre dann uv+beliebige a's und b's ??

15.04.2013, 17:37

Auf diesen Beitrag antworten »

Airblader

Zitat:

also ich kann das schon "übersetzen" was da steht, also es existiert ein u,v aus ...

Na, offenbar ja nicht, denn du scheinst es ja falsch zu übersetzen. Augenzwinkern

Ich mache mich jetzt mal auf den Heimweg, in ca. einer Stunde schreibe ich dann nochmal was.

15.04.2013, 19:13

Auf diesen Beitrag antworten »

Airblader

Bezeichnen wir die Sprache aus Aufgabe 1) mal mit $[latex]\mathcal L[/latex]$ . Die Definition der Sprache sagt dann, dass ein beliebiges Wort $[latex]w \in \Sigma^*[/latex]$ genau dann zur Sprache gehört – also $[latex]w \in \mathcal L[/latex]$ gilt –, wenn es $[latex]u, v \in \Sigma^*[/latex]$ mit [latex]uvw = vwu[/latex]

gibt.
Das ist etwas anderes als was du bisher geschrieben hast und diesen Unterschied solltest du dir klar machen. Der linke Teil gibt sozusagen die "Definitionsmenge" für Wörter der Sprache an, der rechte Teil die Bedingung, die ein Wort aus dieser "Definitionsmenge" erfüllen muss, um zur Sprache zu gehören.

Nochmal: Das mag alles kleinlich klingen, aber diese Grundlagen zu verstehen ist für das Verständnis unglaublich wichtig. Also erst weiterlesen, wenn das verstanden wurde.

Um jetzt mit der Aufgabe ein wenig voranzukommen: Offenbar ist $[latex]w := a \in \Sigma^*[/latex]$ . Stellen wir uns doch mal die Frage, ob $[latex]a \in \mathcal L[/latex]$ gilt.
Wir müssen also $[latex]u, v \in \Sigma^*[/latex]$ finden, so dass die Behauptung erfüllt ist. Ideen?

15.04.2013, 19:27

Auf diesen Beitrag antworten »

Karlito

Zitat:

Original von Airblader
Vielleicht mache ja auch ich einen Fehler, das Studium liegt doch schon ein bisschen zurück…

Ich habe das auch so verstanden, du irrst also nicht. Ich kann mir vorstellen dass die Aufgabe so stimmt, da auch der zweite Teil auf das selbe Verständnis abzielt. Ich möchte das nicht weiter benennen, da es schön wäre, wenn noobee selbst darauf kommt, wie die Aufgabe lösbar ist.

VG,

Karlito

15.04.2013, 19:33

Auf diesen Beitrag antworten »

Airblader

Ich dachte erst, dass vielleicht $[latex]\{w \in \Sigma^* | \exists_{u, v \in \Sigma^+} uvw = vwu\}[/latex]$ gemeint sein könnte, aber ich hatte noch nicht auf die zweite Aufgabe geschaut. Ich denke, dass du recht hast, die Aufgabe ist also wohl doch korrekt. Augenzwinkern

Ich editiere einen Teil oben mal wieder raus, da er unter diesen Umständen zuviel verrät.

15.04.2013, 21:16

Auf diesen Beitrag antworten »

noobee

sooo, jetzt habsch zeit geschockt

also die aufgaben sind richtig abgetippt Zunge raus

ok, nun nochmal hirnschmalz in bewegung setzten. es gibt also dieses w, was aus a,b besteht. wenn nun uvw=vwu sein soll, dann geht das doch mit a,b nur, wenn
u=a, v=a, w=a
oder
u=b, v=b, w=b.

dann wäre uvw=vwu --> aaa=aaa oder eben bbb=bbb, oder ???

ABER, wie kann ww=www sein ?? bei der 2. ist also a!=w, denn aa!=aaa ?!?

15.04.2013, 21:30

Auf diesen Beitrag antworten »

Airblader

Eins nach dem anderen. Wenn du damit sagen willst, dass die erste Sprache nur aus den Wörtern a und b besteht, dann liegst du leider falsch. Hinweis: In $[latex]\Sigma^*[/latex]$ liegt immer ein ganz besonderes Wort, ganz egal wie $[latex]\Sigma[/latex]$ aussieht. Welches ist es und was hat das für Folgen?

Nicht vergessen, dass "a" und "b" nicht die einzigen Wörter sind. "ab", "abba", "abababababab" etc. sind auch alles Wörter.

15.04.2013, 21:41

Auf diesen Beitrag antworten »

noobee

na da liegt doch das leere wort lambda drin, richtig ? mhh, was hätte das für folgen ? gute frage. dann könnte ja das w nicht nur a oder b sein, sondern auch das leere wort. klingt iwie komisch, stimmt das ?

15.04.2013, 21:51

Auf diesen Beitrag antworten »

Airblader

Nein. Was passiert denn, wenn du w = abababba wählst und für u und v jeweils das leere Wort?

15.04.2013, 21:57

Auf diesen Beitrag antworten »

noobee

naja gibt da für mich 2 möglichkeiten:

uvw = lambda,lambda,abababba
vwu = lambda,abababba,lambda - die zwei sind ja nicht die gleichen

oder

ich kann das leere wort lambda weglassen, dann würde rauskommen abababba=abababba ?!?

15.04.2013, 22:00

Auf diesen Beitrag antworten »

Airblader

Was ist denn Lambda? Bezeichnet ihr so das leere Wort? Was ist denn die zentrale Eigenschaft des leeren Wortes?

15.04.2013, 22:06

Auf diesen Beitrag antworten »

noobee

ja, lambda ist bei uns das leer wort. was soll das für eine zentrale eigenschaft haben ? es hat die länge null, wenn du das meinst.

ahh, dann kann ichs also "weglassen", da es ja die länge 0 hat und aus meinem uvw wird nur noch das w übrig bleiben !

15.04.2013, 22:10

Auf diesen Beitrag antworten »

Airblader

Und das heißt nun was für das Wort abababba? Und allgemeiner, für die Sprache?

15.04.2013, 22:21

Auf diesen Beitrag antworten »

noobee

hmmpf, was heißt das für mein abababba, bzw allgemeiner ?
also ich seh da nix besonderes, es sagt mir nix. verwirrt

15.04.2013, 22:23

Auf diesen Beitrag antworten »

Airblader

Was war denn die Frage, die wir uns gestellt hatten?

15.04.2013, 22:29

Auf diesen Beitrag antworten »

noobee

na gesucht waren die wörter, die in/nicht in der menge sigma liegen (wenn uvw=wuv). jetzt könnte man ja meinen, dass, wenn ich u und v = lambda setze, jedes wort (also ab, abbab, abbabbaabb, bbbbbbabbaa, ... ... ...) in dieser menge liegt, da ja die anderen mit der länge null jeweils wegfallen.

ist das der punkt ?

15.04.2013, 22:31

Auf diesen Beitrag antworten »

Airblader

Ganz genau! Die Sprache entspricht also $[latex]\Sigma^*[/latex]$

Jetut zur zweiten Sprache! Findest du ein Wort, das in ihr liegt?

15.04.2013, 22:33

Auf diesen Beitrag antworten »

noobee

huch, das hatteich ganz vergessen. joah, na damit ww=www ist, muss w wohl lambda sein. denn null=null großes Grinsen

15.04.2013, 22:39

Auf diesen Beitrag antworten »

Airblader

Was würde das für die Sprache bedeuten?

15.04.2013, 22:44

Auf diesen Beitrag antworten »

noobee

naja wenn es nur leere worte gibt, wäre das ein sigma^0.
sigma^0={lambda} oder kann ich da sogar schreiben L^0={lambda} ??

L steht für language, sprache

edit: wie schreibe ich denn die sonderzeichen hier ??

15.04.2013, 23:22

Auf diesen Beitrag antworten »

Karlito

Hallo,

"Sonderzeichen" schreibst Du hier in LaTeX. Wie das hier geht, kannst du hier nachlesen.

$[latex] \mathcal{L}^0 = \lambda [/latex]$ ist immer der Fall, da dies für jede Sprache gilt. Die Aussage ist also nicht die, die Du treffen willst.

Versuchs noch mal. Wie ist $[latex] \mathcal{L} [/latex]$ bei Aufgabe 2 gestaltet?

VG,

Karlito

Neue Frage »

Antworten »

alphabete, wörter, sprachen

Verwandte Themen