Grundbegriffe - Versionsgeschichte

Css: /* Wort */

2018-11-04T11:19:38Z

‎Wort

Css: /* Wort */

2018-11-04T10:50:41Z

‎Wort

Css: /* Wort */

2018-11-04T10:46:24Z

‎Wort

Jana: Zahlendreherfix

2018-08-26T14:39:09Z

Zahlendreherfix

Css: /* Codierung als Zahlen */

2018-07-21T22:16:23Z

‎Codierung als Zahlen

Css: /* Codierung als Zahlen */

2018-07-21T22:12:49Z

‎Codierung als Zahlen

Css am 21. Juli 2018 um 22:10 Uhr

2018-07-21T22:10:45Z

Css am 21. Juli 2018 um 21:04 Uhr

2018-07-21T21:04:34Z

Css am 21. Juli 2018 um 20:59 Uhr

2018-07-21T20:59:53Z

Css: /* Wort */

2018-07-21T20:50:58Z

‎Wort

@@ Zeile 20: / Zeile 20: @@
 * $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$
 * $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
-* Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jeder Sprache. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einer Sprache $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.
+* Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jedem Alphabet. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einem Alphabet $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.
 * '''TODO'''

@@ Zeile 13: / Zeile 13: @@
 == Wort ==
-Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.
+Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einem Alphabet $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.
 Beispiele:

@@ Zeile 13: / Zeile 13: @@
 == Wort ==
-Als '''Wort''' über einer Sprache $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.
+Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.
 Beispiele:

@@ Zeile 46: / Zeile 46: @@
 Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.
-Das Wort $)($ bekäme die Zahl $6\cdot 16+5=101$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.
+Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.
 Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.

← Nächstältere Version		Version vom 21. Juli 2018, 22:16 Uhr
Zeile 46:		Zeile 46:
	Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.		Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.

−	Das Wort $)($ bekäme die Zahl $6\cdot 16+5=101$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6$ zugeordnet.	+	Das Wort $)($ bekäme die Zahl $6\cdot 16+5=101$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.
		+
		+	Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.

@@ Zeile 44: / Zeile 44: @@
 Beweis: Übung.
-Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1,-\rightarrow 2,\cdot\rightarrow 3,\div\rightarrow 4, (\rightarrow 5, )\rightarrow 6, 0\rightarrow 7, 1\rightarrow 8, 2\rightarrow 9, 3\rightarrow 10, 4\rightarrow 11, 5\rightarrow 12, 6\rightarrow 13, 7\rightarrow 14, 8\rightarrow 15, 9\rightarrow 16\}$.
+Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.
 Das Wort $)($ bekäme die Zahl $6\cdot 16+5=101$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6$ zugeordnet.

@@ Zeile 37: / Zeile 37: @@
 * '''TODO'''
-== Die Cantor'sche Paarungsfunktion ==
+== Codierung als Zahlen ==
-'''TODO'''
+Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.
-== Codierung als Zahlen ==
+Lemma: Diese Zuordnung ist Bijektiv.
-Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[0;n-1]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [0;n-1]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen.
+Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1,-\rightarrow 2,\cdot\rightarrow 3,\div\rightarrow 4, (\rightarrow 5, )\rightarrow 6, 0\rightarrow 7, 1\rightarrow 8, 2\rightarrow 9, 3\rightarrow 10, 4\rightarrow 11, 5\rightarrow 12, 6\rightarrow 13, 7\rightarrow 14, 8\rightarrow 15, 9\rightarrow 16\}$.
-Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen.
+Das Wort $)($ bekäme die Zahl $6\cdot 16+5=101$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6$ zugeordnet.

← Nächstältere Version		Version vom 21. Juli 2018, 20:59 Uhr
Zeile 36:		Zeile 36:
	* Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.		* Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.
	* '''TODO'''		* '''TODO'''
		+
		+	== Codierung als Zahlen ==
		+
		+	Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[0;n-1]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [0;n-1]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen, und diese Zuordnung ist eineindeutig zwischen ${\cal L}^*$ und $\mathbb{N}$.

@@ Zeile 23: / Zeile 23: @@
 * '''TODO'''
-Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\epsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.
+Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.
 == Sprache ==