Kreuzprodukt und Alphabete < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:21 Mo 26.05.2008 | | Autor: | Parkan |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Seien A = { x [mm] \in \IN [/mm] | 1 [mm] \le [/mm] x [mm] \le [/mm] 100 } und B = {a,b,c,d}
1. Wieviele Elemente hat A x B?
2. Seien Z und G Alphabete, Gilt für beliebige Mengen C [mm] \subseteq [/mm] Z* und D [mm] \subseteq [/mm] G* die Gleichung |C * D| = |C x D| ? Begründe deine Antwort
|
Ich nehm an, bei
1. Ist das ein Kreuzprodukt. Hat das dann 5 Elemente ? (x Kreuzt a, b, c, d) oder muss ich 4 natrüliche Zahlen nehmen z.B. (1,2,3,4 x a,b,c,d) ? Ich verstehe die Aufgabenstellung nicht ganz, hoffe jemand kann mir da ein Einleuchtendes Beispiel oder Tipp geben.
Bei
2. Würde ich sagen ist [mm] \not= [/mm] da man verschiedene Rechenoperationen macht. Denn |x+x| [mm] \not= [/mm] |x kreuzt x| x [mm] \in \IN. [/mm] Ich habe mir gerade dazu 2 Alphabete ausgedacht am ende habe ich C= ab, ba, ac und für D= de, df, ed
Wie würde den hier |C*D| und |CxD| aussehen? Aufjedenfall würden die noch nichtg = sein oder?
Danke für die Tipps
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo Parkan!
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
>
> Seien A = { x [mm]\in \IN[/mm] | 1 [mm]\le[/mm] x [mm]\le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
100 } und B =
> {a,b,c,d}
>
> 1. Wieviele Elemente hat A x B?
> 2. Seien Z und G Alphabete, Gilt für beliebige Mengen C
> [mm]\subseteq[/mm] Z* und D [mm]\subseteq[/mm] G* die Gleichung |C * D| = |C
> x D| ? Begründe deine Antwort
>
> Ich nehm an, bei
> 1. Ist das ein Kreuzprodukt. Hat das dann 5 Elemente ? (x
> Kreuzt a, b, c, d) oder muss ich 4 natrüliche Zahlen
> nehmen z.B. (1,2,3,4 x a,b,c,d) ? Ich verstehe die
> Aufgabenstellung nicht ganz, hoffe jemand kann mir da ein
> Einleuchtendes Beispiel oder Tipp geben.
Nein, du musst jeweils ein Element von A nehmen und es mit einem Element von B kreuzen. Und das für alle Elemente aus A und alle Elemente aus B, also jedes mit jedem. Kleineres Beispiel: [mm] A=\{1,2\}, B=\{a\}, [/mm] ergibt dann: [mm] $A\times B=\{(1,a), (2,a)\}$. [/mm] Bekommst du das jetzt auf deine Aufgabe übertragen?
> Bei
> 2. Würde ich sagen ist [mm]\not=[/mm] da man verschiedene
> Rechenoperationen macht. Denn |x+x| [mm]\not=[/mm] |x kreuzt x| x
> [mm]\in \IN.[/mm] Ich habe mir gerade dazu 2 Alphabete ausgedacht
> am ende habe ich C= ab, ba, ac und für D= de, df, ed
> Wie würde den hier |C*D| und |CxD| aussehen? Aufjedenfall
> würden die noch nichtg = sein oder?
Was ist denn mit C*D gemeint? Soll das die Konkatenation sein, also erst ein Element von C und dann eins von D? Dann wäre ich auch der Meinung, dass das beides ungleich ist, meine solch eine Aufgabe auch mal gehabt zu haben, habe ansonsten aber gerade nicht näher drüber nachgedacht. Warum du allerdings für dein Beispiel so komplizierte Alphabete nimmst, weiß ich nicht. Probiere es doch hier auch mal mit etwas einfachem wie meinem Beispiel oben...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:18 Di 27.05.2008 | | Autor: | nikito |
Hallo Parkan,
den ersten Teil hat ja Bastiane schon richtig erklärt. Nun zum zweiten Teil. Erstens ist nicht die Frage ob C*D = CxD sondern ob die beiden Mengen die diese Operationen liefern die gleiche Kardinalität haben. Also ob sie gleich viele Elemente besitzen.
Was ist denn Z*? Das ist die kleene-Hülle über dem Alphabet Z. Eine formale Definition wäre für [mm] Z=\{w_1,...,w_n\} [/mm] ist Z*= [mm] \bigcup_{i\ge0}Z^i=\{z_1*...*z_m|z_j \in Z,m \in \IN_0\}. [/mm]
Ein Beispiel: Z={0,1} dann wäre Z* die Menge aller möglichen Binärcodierungen [mm] \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, ....\} [/mm] wobei [mm] \varepsilon [/mm] das leere Wort ist.
Somit sind C, D Mengen von Worten genannt Sprachen. Die Operation "*" auf diesen Sprachen liefert die Produktsprache C*D = [mm] \{c*d| c\in C, d\in D\}
[/mm]
Somit liefert C*D die Menge aller Möglichen Konkatenationen c*d und CxD eine Menge von Tupel (c,d) mit c [mm] \in [/mm] C und [mm] d\in [/mm] D. Zu jeder möglichen Konkatenation existiert ein korrespondierendes Tupel und umgekehrt. Folglich haben sie die gleiche Kardinalität und es gilt |C*D|=|CxD|.
Beweisen kann man das auch über die vollständige Induktion aber das ist hier ja nicht gefordert. Steht ja zum Glück nur da "begründe dein Antwort" ;) Ein schönes Thema die Formalen Sprachen.
Ich hoffe das hat dir weitergeholfen.
Lg Nikito
|
|
|
|
