(Un-)endliche Sprachen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seinen [mm] \Sigma_1 [/mm] und [mm] \Sigma_2 [/mm] Alphabete. D.h. [mm] \Sigma_1 [/mm] und [mm] \Sigma_2 [/mm] sind nicht-leere endliche Mengen von Symbolen.
Beweisen oder widerlegen Sie:
1. [mm] \Sigma_1^x \bigcup \Sigma_2^x [/mm] ist unendlich
2. [mm] \Sigma_1^x \bigcap \Sigma_2^x [/mm] ist unendlich |
Allgmein stellt sich mir die Frage, ob die nicht leere Menge von Symbolen auch aus [mm] \epsilon [/mm] bestehen darf, was meine Beweis zerreißen würde.
Ansonsten wüsste ich gerne, ob mein Beweis so hinkommt:
[mm] \paragraph{(1)}
[/mm]
Sei [mm] $\Sigma_1 [/mm] = [mm] \{ A \}$ [/mm] die kleinste nicht-leere, endliche Menge, wobei A ein beliebiges Symbol repräsentiert.
[mm] $\Sigma_1^x$ [/mm] ist die Menge der Worte, die man aus Symbolen der Menge [mm] $\Sigma_1$ [/mm] bilden kann. [mm] \\ \\
[/mm]
Da man das Symbol A beliebig oft aneinanderfügen kann ("A","AA","AAA","AAAA") ergibt sich, dass [mm] $\Sigma_1^x$ [/mm] unendlich ist. [mm] \\ \\
[/mm]
Da [mm] $\Sigma_1^x \subseteq (\Sigma_1^x \bigcup \Sigma_2^x)$ [/mm] folgt, dass [mm] $\Sigma_1^x \bigcup \Sigma_2^x$ [/mm] ebenfalls unendlich ist (q.e.d.).
[mm] \paragraph{(2)}
[/mm]
Seien [mm] $\Sigma_1 [/mm] = [mm] \{A \}, \Sigma_2 [/mm] = [mm] \{B\}$ [/mm] nicht-leere, endliche Mengen an Symbolen, wobei A und B zwei beliebige voneinander verschiedene Symbole repräsentieren. [mm] \\ \\
[/mm]
Wörter in [mm] $\Sigma_1^x\bigcap \Sigma_2^x$ [/mm] können nur aus Symbolen der Schnittmenge [mm] $\Sigma_1 \bigcap \Sigma_2$ [/mm] bestehen. [mm] \\ \\
[/mm]
Es ist aber [mm] $\Sigma_1 \bigcap \Sigma_2 [/mm] = [mm] \{ \epsilon \}$. [/mm] Somit folgt, dass [mm] $\Sigma_1^x \bigcap \Sigma_2^x$ [/mm] nur das leer Wort enthält und somit nicht unendlich ist (q.e.d).
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:21 Fr 07.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
