Formale Sprachen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:29 So 13.04.2008 | | Autor: | vohigu |
| Aufgabe | Sein im folgendem [mm] \summe [/mm] = {a,b}. Es wird die Menge L [mm] \subset \summe [/mm] Stern mit den folgenden Eigenschaften betrachtet.
-a [mm] \in [/mm] L
-Falls sich ein beliebiges Wort x in L befindet (x [mm] \in [/mm] L), so befinden sich auch die Worte
aax,abx,bax,bbx in L. (aax,abx,bax,bbx [mm] \in [/mm] L). Also : [mm] \forall [/mm] x [mm] \in [/mm] L [mm] \Rightarrow [/mm] aax,abx,bax,bbx [mm] \in [/mm] L
(a) geben Sie [mm] \summe1 \cap [/mm] L, [mm] \summe² \cap [/mm] L, [mm] \summe³ \cap [/mm] L, [mm] \summe4 \cap [/mm] L, [mm] \summe5 \cap [/mm] L an. |
Hi, ich weiss schon soviel dass L eine sprache ist, aber was heißt das? L = {a, b, aa, bb, ....}? Was stellt L dar bzw. welche Elemente befinden sich wirklich in L?
-a [mm] \in [/mm] L: soll das heißen dass a das einzige Element von L ist?
Meine Frage ist eher kann mir jemand das hier erklären, aber bitte auf einfache weise mit einem Beispiel.
Dank euch!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:07 So 13.04.2008 | | Autor: | pelzig |
Muss dazu sagen ich hab nur die Wikipedia-Artikel zum Thema gelesen. Hier also ein paar Denkanstöße - keine Garantie dass hier irgendwas stimmt. ^^
> Sein im folgendem [mm]\summe[/mm] = {a,b}. Es wird die Menge L
> [mm]\subset \summe[/mm] Stern mit den folgenden Eigenschaften
> betrachtet.
Ich nehme an [mm] $\Sigma^\*$ [/mm] ist die Kleensche Hülle über unserem Alphabet [mm] $\Sigma$.
[/mm]
> -a [mm]\in[/mm] L
> -Falls sich ein beliebiges Wort x in L befindet (x [mm]\in[/mm] L),
> so befinden sich auch die Worte
> aax,abx,bax,bbx in L. (aax,abx,bax,bbx [mm]\in[/mm] L). Also :
> [mm]\forall[/mm] x [mm]\in[/mm] L [mm]\Rightarrow[/mm] aax,abx,bax,bbx [mm]\in[/mm] L
Nehme an das ist dann sozusagen die Grammatik unserer Sprache (?)
> (a) geben Sie [mm]\summe1 \cap[/mm] L, [mm]\summe² \cap[/mm] L, [mm]\summe³ \cap[/mm]
> L, [mm]\summe4 \cap[/mm] L, [mm]\summe5 \cap[/mm] L an.
Also ich nehme an mit [mm] $\Sigma^k$ [/mm] meinst du die k-fache Konkatenation von [mm] $\Sigma$ [/mm] mit sich selbst.
> Hi, ich weiss schon soviel dass L eine sprache ist, aber
> was heißt das? L = {a, b, aa, bb, ....}? Was stellt L dar
> bzw. welche Elemente befinden sich wirklich in L?
Also rein Formal ist L einfach eine Menge von Worten, die eben dieser Grammatik genügt. Natürlich sind da unendlich viele Worte drin (deshalb steht da ja auch "..."), also kannst du auch nie alle Elemente aufschreiben, die da wirklich drin sind, aber wenn dir jemand ein Wort sagt kannst du untersuchen und entscheiden, ob es in der Menge liegt oder nicht, d.h. der Grammatik genügt oder nicht.
> -a [mm]\in[/mm] L: soll das heißen dass a das einzige Element von L
> ist?
Nein, es heißt dass $a$ ein Element von L ist, es kann weitere geben, muss es aber nicht.
> Meine Frage ist eher kann mir jemand das hier erklären,
> aber bitte auf einfache weise mit einem Beispiel.
Also ein Beispiel:
(a): [mm] $\Sigma^2=\{a,b\}^2=\{a,b\}^1\circ\{a,b\}=(\{a,b\}^0\circ\{a,b\})\circ\{a,b\}=(\{\epsilon\}\circ\{a,b\})\circ\{a,b\}=\{a,b\}\circ\{a,b\}=\{aa,ab,ba,bb\}$
[/mm]
Hier hab ich einfach nach Definition [mm] $\Sigma^2$ [/mm] ausgerechnet. Was ist nun mit [mm] $\Sigma^2\cap [/mm] L$?
Dazu schaust du dir jedes Wort aus [mm] $\Sigma^2$ [/mm] an und guckst, ob es auch in $L$ liegt:
"aa" liegt in L, denn da das leere Wort [mm] $x=\epsilon$ [/mm] liegt in L, und somit auch $aax=aa$.
(usw.)
Ein Wort, das z.B. nicht in L liegt wäre "bbb". Wenn man sich die Grammatik anschaut sieht man, dass kein Wort von ungerader Länge, das mit "b" endet, in L liegt. Jedoch liegt jedes Wort mit gerade Wortlänge in L. (Hoffe das stimmt jetzt mal ^^)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:45 So 13.04.2008 | | Autor: | fox1612 |
woher weisst du denn dass das leere Wort x = e in L liegt? das ist doch nirgends definiert? es könnte doch auch seien, dass L lediglich aus dem element a besteht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:09 So 13.04.2008 | | Autor: | pelzig |
> woher weisst du denn dass das leere Wort x = e in L liegt?
> das ist doch nirgends definiert?
Mit dem leeren Wort haste recht. Hab halt leider keine richtige Defintion einer formalen Sprache gefunden und einfach angenommen, jede formale Sprache enthält das leere Wort. Ich hätte das erwähnen sollen aber es ging ja auch eher darum mal ein bischen mit der Aufgabe rumzuspielen, damit vohigu mal sieht wie man damit umgeht.
> es könnte doch auch seien,
> dass L lediglich aus dem element a besteht?
Also $L={a}$, kann nicht sein, denn dann müsste z.B. auch [mm] $aaa\in [/mm] L$ sein.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:14 So 13.04.2008 | | Autor: | pelzig |
Was mir auch noch aufgefallen ist, allein aus den Voraussetzungen
(i) [mm] $a\in [/mm] L$
(ii) [mm] $\forall x\in L\Rightarrow [/mm] aax, abx, bax, [mm] bbx\in [/mm] L$
lässt sich [mm] $b\in [/mm] L$ weder beweisen noch widerlegen. Insbesondere erfüllt auch [mm] $\Sigma^\*$ [/mm] selbst die Voraussetzungen. Das is irgendwie schlecht, denn dann könnte man ja auch über [mm] $bbb\in [/mm] L$ auch keine Aussage machen... Insofern ist L nichtmal ne richtige Menge, oder gibt es da irgend ne Konvention die ich nicht kenne? Was meinen die anderen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:50 So 13.04.2008 | | Autor: | vohigu |
Die Aufgabe steht genau so auf meinem Aufgabenblatt. Und wie du schon sagtest es ist nichts genau definiet, das ist es auch was mir ja so Probleme bei der definierung einer Lösung macht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:13 So 13.04.2008 | | Autor: | pelzig |
Also ich hab jetzt nochmal ein bischen nachgelesen. Wenn man also wirklich von unserem mathematisch-mengentheoretischen Standpunkt herangeht, existiert die Menge L einfach nicht, denn man kann beispielsweise nicht entscheiden, ob [mm] $b\in [/mm] L$ liegt. Man könnte höchstens die kleinste Menge, also der Schnitt aller Mengen die die Voraussetzungen erfüllen, betrachten...
Wenn man aber den Standpunkt der Fomalen Sprachen betrachtet, dann interessiert dich natürlich nur die von der Grammatik erzeugt Sprache. Eine Grammatik besitzt immer ein Startsymbol (vgl. http://de.wikipedia.org/wiki/Formale_Grammatik), da das hier nicht explizit erwähnt wird könnte man "a" als solches interpretieren.
Am besten du machst dir das Leben nicht zu schwer und nimmst einfach an es sind halt alle Wörter in L, die sich aus "a" durch diese Regeln bilden lassen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:21 Di 15.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
