alphabete, wörter, sprachen |
noobee unregistriert
|
|
alphabete, wörter, sprachen |
|
zwei aufgaben, bei denen ich icht wei wie ich anfangen soll bzw was zu machen ist
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:48 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
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?
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
15.04.2013 10:19 |
|
|
noobee
Jungspund
Dabei seit: 15.04.2013
Beiträge: 11
|
|
naja also ich denke einfach mal laut
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 10:46 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
Ah, das Problem liegt also woanders.
beschreibt die Sprache aller Wörter mit der Eigenschaft, dass es gibt, so dass 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?
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
15.04.2013 11:37 |
|
|
noobee
Jungspund
Dabei seit: 15.04.2013
Beiträge: 11
|
|
Zitat: |
Hilft das schon weiter? |
mhh, will ja nicht unhöflich sein, aber "nein", hilft nicht weiter
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 15:21 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
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.
Ich mache mich jetzt mal auf den Heimweg, in ca. einer Stunde schreibe ich dann nochmal was.
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
15.04.2013 17:37 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
Bezeichnen wir die Sprache aus Aufgabe 1) mal mit . Die Definition der Sprache sagt dann, dass ein beliebiges Wort genau dann zur Sprache gehört – also gilt –, wenn es mit 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 . Stellen wir uns doch mal die Frage, ob gilt.
Wir müssen also finden, so dass die Behauptung erfüllt ist. Ideen?
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Airblader: 15.04.2013 19:34.
|
|
15.04.2013 19:13 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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:27 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
Ich dachte erst, dass vielleicht 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.
Ich editiere einen Teil oben mal wieder raus, da er unter diesen Umständen zuviel verrät.
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
15.04.2013 19:33 |
|
|
noobee
Jungspund
Dabei seit: 15.04.2013
Beiträge: 11
|
|
sooo, jetzt habsch zeit
also die aufgaben sind richtig abgetippt
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 ?!?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von noobee: 15.04.2013 21:17.
|
|
15.04.2013 21:16 |
|
|
noobee
Jungspund
Dabei seit: 15.04.2013
Beiträge: 11
|
|
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:41 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
Nein. Was passiert denn, wenn du w = abababba wählst und für u und v jeweils das leere Wort?
__________________ The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
15.04.2013 21:51 |
|
|
noobee
Jungspund
Dabei seit: 15.04.2013
Beiträge: 11
|
|
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 21:57 |
|
|
|
|
|
|
|