Datenverarbeitende Systeme:
Kapitel 1: Grundlagen
1.1 Bezeichnungen
Wir definieren zunächst einige Bezeichner:
Es sei N = { 1, 2, 3, . . . } eine Menge natürlicher Zahlen
Es sei N0 = { 0, 1, 2, . . . } eine Menge N inclusive Null
Es sei Z = { ..., -2, -1, 0, 1, 2, ... } eine Menge ganzer Zahlen
Es sei M eine beliebige Menge, dann heißt R auf M x M Relation auf M.
Sprich: Zwei Elemente (jeweils aus der Menge M entnommen) stehen miteinander in einer
Relation R.
Eine Relation wäre zum Beispiel die < - Operation ( z.B. 3 < 4 ).
Eine Relation R auf M nennen wir Äquivalenzrelation, wenn für Elemente x,y,z
aus der Menge M gilt:
(x, x) E R (Reflexivität) [z.B. x = x ]
(x, y) E R => (y, x) E R (Symmetrie) [z.B. x = y => y = x]
(x, y) E R und (y, z) E R => (x, z) E R (Transitivität) [z.B. x = y und y = z => x = z ]
Der Ausdruck E R bedeutet: ist Element der Relation R. In den obigen Beispielen habe ich also als Relation
den Gleichheitsoperator verwendet. Der Kleiner-als - Operator wäre keine Äquivalenzrelation, da
er nicht symmetrisch ist: aus 3 < 4 folgt nicht 4 < 3 !
1.2 Vollständige Induktion
Das Prinzip der vollständigen Induktion ist ein Mittel der mathematischen Beweißführung.
Damit lässt sich für Aussagen A(n) prüfen, ob A(n) wahr ist für n > n0. Dazu muss
man zunächst durch Rechnung zeigen, dass A für n0 richtig ist. Dann müssen wir daraus schließen,
dass aus A(n) => A(n+1) folgt. Wir sprechen von Induktionsanfang und Induktionsschluß oder -schritt.
1.3 Bezeichnungen aus den Grundlagen der Informatik
Sei S eine endliche Menge ohne die leere Menge {}, S heißt Alphabet
Ein Element s aus dem Alphabet S nennen wir Symbol.
Eine Kette von Symbolen s = s1 s2 . . . sn nennen wir Wort über S
Wir nennen S* die Menge aller Wörter über S
|s| sei die Länge des Wortes s := Anzahl der Symbole im Wort s
|s|t sei die Anzahl des Auftretens des Symbols t im Wort s
Zwei Wörter s und t können miteinander verbunden werden. Die entsprechende Operation nennt man
Konkatenation von s mit t. Wir schreiben dafür kat(s, t) oder einfach st. Die Konkatenation
ist eine Abbildung von S* x S* ---> S* (kat bildet zwei Elemente aus S* wieder auf ein Element aus
S* ab).
Kat ist eine Assoziative Verknüpfung auf S*, d.h. (st)u = s(tu). (S*, kat) ist eine Halbgruppe.
Nimmt man das leere Wort {} ub die Menge S* hinein, so erhält man S+ und damit einen Monoiden
(S+, kat). {} ist dabei das neutrale Element.
Definition:
(S+, kat) heißt Wörtermonoid über S
(S*, kat) heißt Wörterhalbgruppe über S
Eine Teilmenge L aus S* heißt (formale) Sprache über S
Sn sei die Menge aller Wörter s aus S+ mit der Länge n.
|